Математическая логика и теория алгоритмов. Галуев Г.А. - 6 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 6 из 64
© 2003 Галуев Геннадий Анатольевич
Эквивалентность пропозиционных форм.
Каждая пропозиционная форма определяет некоторую булеву (истинностную)
функцию, однако одной и той же функции могут соответствовать несколько пропози-
ционных форм.
О
О
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
е
е
.
. Если пропозиционная форма при любых истинностных значениях
принимает значение «истина» то она называется тождественно истинным высказыва-
нием или
тавтологией.
О
О
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
е
е
.
. Если пропозиционная форма при любых истинностных значениях
своих букв принимает значение «ложь», то она называется тождественно ложным вы-
сказыванием или противоречием.
О
О
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
е
е
.
. Эквивалентными будем называть пропозиционные
формы, кото-
рым соответствует одна и та же истинностная функция, т.е. таблица истинности.
Если А эквивалентно В, то будем это обозначать (А↔В).
Здесь пропозиционная
форма (А↔В) является тавтологией, т.е. её таблица истинности содержит на всех
возможных наборах переменных А и В только значения истины, т.е. 1. Например, фор-
мула ((А→В)↔((⎤А)
∨
В))
является тавтологией и она принимает только 1 значение.
А В (⎤А) ((⎤А)
∨ В) (А→В) ((А→В)↔((⎤А) ∨ В))
1 1 0 1 1 1
1 0 0 0 0 1
0 1 1 1 1 1
0 0 1 1 1 1
Табл. 1
Последний столбец таблицы содержит только значение 1, поэтому формула
((А→В)↔((⎤А)
∨ В)) является тавтологией, а высказывание А→В и (⎤А)∨ В являются эк-
вивалентными. Таким образом, таблицы истинности позволяют установить являются ли
два высказывания эквивалентными или является ли некоторое высказывание тождест-
венно истинным, т.е. тавтологией.
В исчислении высказываний для доказательства теорем требуется иметь способ
целенаправленного перехода от одних пропозиционных форм к другим эквивалентным
им формам. Указанный выше метод построения таблиц
для установления эквивалент-
ности высказываний является громоздким. Поэтому в математической логике использу-
ется другой подход, основанный на свойствах введённых пропозиционных связок ⎤, &,
∨ , →, ↔ и следующих двух теоремах.
Т
Т
е
е
о
о
р
р
е
е
м
м
а
а
.
. Если А есть тавтология, содержащая пропозиционные буквы А
1
,…,А
n
и В
получается из А подстановкой в А пропозиционных форм А
′
n
,…,А
′
n
вместо А
n
,…,А
n
соот-
ветственно, то В есть тавтология, т.е. подстановка в тавтологию приводит к тавтологии.
Доказательство.
Предположим, что А есть тавтология и пусть задано произвольное распределение
истинностных значений пропозиционных букв, входящих в В. Формы А
′
n
,…,А
′
n
примут
некоторое значение X
1
,…,X
n
(каждое X
j
есть 0 или 1); если мы придадим значения
X
1
,…,X
n
соответственно буквам А
n
,…,А
n
, то очевидно значение А совпадёт с истинност-
ным значением В при заданном распределении значений букв, входящих в В. Так как А
есть тавтология, то В при этом распределении значений своих аргументов примет зна-
чение 1. Таким образом В всегда принимает значение 1.
Эта теорема позволяет нам в тавтологии, любую пропозиционную букву заменить
на произвольную (одну и ту же для каждого вхождения этой буквы) пропозиционную
форму.
Т
Т
е
е
о
о
р
р
е
е
м
м
а
а
.
. Если В
1
получается из А
1
подстановкой В вместо одного или большего
числа вхождений А и если А и В эквивалентны, то и А
1
и В
1
эквивалентны.

Страницы