![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Необходимость: Пусть формулы и
равносильны. Тогда, по определению, для любого набора значений пропозиционных переменных
,
,...,
формулы
и
принимают одинаковые истинностные значения. Это значит, что высказывания
и
будут либо оба истинны, либо оба ложны. В обоих случаях эквивалентность
истинна. Следовательно, исходная формула есть тавтология.
Достаточность: Пусть формула в условии теоремы есть тавтология, тогда для любого набора значений пропозиционных переменных, например, ,
,...,
её значение будет «истина», т.е. эквивалентность
есть истинное высказывание. Следовательно, высказывания
и
либо оба истинны, либо оба ложны. Таким образом, для любых значений пропозиционных переменных формулы
и
принимают одинаковые истинностные значения, поэтому они равносильны. Теорема доказана.
Основная цель в логике высказываний – это поиск тавтологий (общезначимых или тождественно-истинных формул). При построении произвольной теории обычно выбирают систему аксиом. Каждая аксиомы – это тавтология. Логическая структура теорем – это тавтология. Поэтому, поиск новых аксиом – актуальная задача. Для обозначения тавтологий будем использовать символ: ╞.
Рассмотрим несколько правил построения новых тавтологий из уже существующих. Зная ограниченное число простых тавтологий и несколько таких правил, можно вывести большое количество различных общезначимых формул.
Первое правило основано на теореме.
Теорема 5: Пусть - произвольная формула,
- формула, получаемая из
подстановкой формулы
вместо простого компонента
везде, где он встречается в
. Тогда, если ╞
, то ╞
.
Замечание: Далее будем считать эквивалентные формулы взаимозаменяемыми.
Рассмотрим второе правило построения тавтологий непосредственным путем. Сначала рассмотрим формулы, построенные из пропозиционных переменных с помощью операций
.
Определение 7: Формула называется негативом формулы
, если она получена заменой каждого вхождения
на символ
и наоборот и заменой каждого вхождения
на выражение
и наоборот.
Например, негативом формулы есть формула
.
Нижеследующая теорема связывает понятия негатива и тавтологии.
Теорема 6: Пусть есть формула, построенная из пропозиционных переменных только с помощью операций
. Пусть
есть негатив формулы
. Тогда ╞
.
Замечание: Выше было показано, что операции можно исключить из любой формулы. Система логических связок
является полной. Значит, теорему 6 можно применять гораздо шире.
Вместо построения таблицы истинности для произвольной формулы можно применять арифметические процедуры. Основой для такого подхода служат следующие соглашения:
1. И = 1, Л = 0.
2. Каждая пропозиционная переменная принимает значения 0 или 1. При этом формула интерпретируется как истинностная функция.
3. Суммы и произведения, в которые входят слагаемые и сомножители 0 и 1, подсчитываются как в обычной арифметике за одним исключением: 1+1=0.
Принимая во внимание все выше сказанное, находим, что основные истинностные функции задаются следующими формулами:
,
,
,
,
.
В этих терминах тавтологиями будут те функции, которые тождественно равны 1.
Дата публикования: 2014-11-03; Прочитано: 403 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!