Доказательство. - раздел Математика, КУРС ЛЕКЦИЙ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ Необходимость: Пусть Формулы ...
Необходимость: Пусть формулы и равносильны. Тогда, по определению, для любого набора значений пропозиционных переменных , ,..., формулы и принимают одинаковые истинностные значения. Это значит, что высказывания и будут либо оба истинны, либо оба ложны. В обоих случаях эквивалентность истинна. Следовательно, исходная формула есть тавтология.
Достаточность: Пусть формула в условии теоремы есть тавтология, тогда для любого набора значений пропозиционных переменных, например, , ,..., её значение будет «истина», т.е. эквивалентность есть истинное высказывание. Следовательно, высказывания и либо оба истинны, либо оба ложны. Таким образом, для любых значений пропозиционных переменных формулы и принимают одинаковые истинностные значения, поэтому они равносильны. Теорема доказана.
Основная цель в логике высказываний – это поиск тавтологий (общезначимых или тождественно-истинных формул). При построении произвольной теории обычно выбирают систему аксиом. Каждая аксиомы – это тавтология. Логическая структура теорем – это тавтология. Поэтому, поиск новых аксиом – актуальная задача. Для обозначения тавтологий будем использовать символ: ╞.
Рассмотрим несколько правил построения новых тавтологий из уже существующих. Зная ограниченное число простых тавтологий и несколько таких правил, можно вывести большое количество различных общезначимых формул.
Первое правило основано на теореме.
Теорема 5: Пусть - произвольная формула, - формула, получаемая из подстановкой формулы вместо простого компонента везде, где он встречается в . Тогда, если ╞ , то ╞ .
Замечание: Далее будем считать эквивалентные формулы взаимозаменяемыми.
Рассмотрим второе правило построения тавтологий непосредственным путем. Сначала рассмотрим формулы, построенные из пропозиционных переменных с помощью операций .
Определение 7: Формула называется негативом формулы , если она получена заменой каждого вхождения на символ и наоборот и заменой каждого вхождения на выражение и наоборот.
Например, негативом формулы есть формула .
Нижеследующая теорема связывает понятия негатива и тавтологии.
Теорема 6: Пусть есть формула, построенная из пропозиционных переменных только с помощью операций . Пусть есть негатив формулы . Тогда ╞ .
Замечание: Выше было показано, что операции можно исключить из любой формулы. Система логических связок является полной. Значит, теорему 6 можно применять гораздо шире.
Вместо построения таблицы истинности для произвольной формулы можно применять арифметические процедуры. Основой для такого подхода служат следующие соглашения:
1. И = 1, Л = 0.
2. Каждая пропозиционная переменная принимает значения 0 или 1. При этом формула интерпретируется как истинностная функция.
3. Суммы и произведения, в которые входят слагаемые и сомножители 0 и 1, подсчитываются как в обычной арифметике за одним исключением: 1+1=0.
Принимая во внимание все выше сказанное, находим, что основные истинностные функции задаются следующими формулами:
,
,
,
,
.
В этих терминах тавтологиями будут те функции, которые тождественно равны 1.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ... ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ... имени ВЛАДИМИРА ДАЛЯ...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Доказательство.
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Упражнения для самостоятельной работы.
1. Даны следующие высказывания:
P = «Данное число – целое»,
Q = «Данное число – положительное»,
R = «Данное число – простое»,
S = «Данное число
Формулы алгебры логики. Тавтологии.
В алгебре выводятся формулы, которые остаются верными, какие бы числа не подставляли вместо букв, входящих в эти формулы. Подобным образом в алгебре высказываний конструируются формулы из некоторых
Алгоритм преобразования произвольной формулы в СНДФ.
1) Выразить все логические операции через конъюнкцию, дизъюнкцию и отрицание.
2) Используя дистрибутивные законы, преобразовать формулу так, чтобы все конъюнкции выполнялись раньше дизъюнк
Определения.
В математике принято одной и той же буквой обозначать различные объекты, т. е. под буквой фактически понимается переменная, принимающая значения из некоторого множества. Такие перем
Упражнения для самостоятельной работы.
1. Записать следующие высказывания в виде формул логики предикатов.
1) Всякое натуральное число, делящееся на 12, делится на 2, 4 и
Упражнения для самостоятельной работы.
1.Записать на языке логики предикатов аксиому математической индукции.
2. Записать на языке логики предикатов следующую те
Формальный язык логики высказываний.
Таблицы истинности в логике высказываний позволяют ответить на многие вопросы. Например, является ли данная формула тавтологией, противоречием или выполнимой формулой; влечёт ли она
Теорема Поста.
В предыдущем параграфе были рассмотрены некоторые классы булевых функций. В каждый класс попадают функции, обладающие определённым свойством. Для удобства введём сле
Новости и инфо для студентов