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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 7 из 64
© 2003 Галуев Геннадий Анатольевич
Доказательство.
Рассмотрим произвольное распределение истинностных значений для пропозици-
онных букв. Так как А и В эквивалентны, т.е. принимают одинаковые истинностные
значения, то одинаковые истинностные значения примут также А
1
и В
1
, поскольку В
1
отличается от А
1
только тем, что в некоторых местах вместо В содержится А.
Эта теорема даёт возможность получения из любой формы А
1
эквивалентной ей
формы В
1
, путём подстановки в первую (в А
1
) вместо некоторой пропозиционной фор-
мы А эквивалентной ей пропозиционной формы В.
Таким образом, теоремы 1 и 2 дают возможность производить подстановки в про-
позиционные формы, получая при этом формы эквивалентные исходным.
Прочтение сложных пропозиционных форм (формул) может стать неоднозначным,
если не ввести соглашения об употреблении скобок в записях этих форм.
Примем следующее
соглашение:
Во-первых, будем опускать в пропозиционной форме внешнюю пару скобок.
Во-вторых, если форма содержит вхождения только одной пропозиционной бинар-
ной связки (например →, или ↔, или &), то для каждого вхождения этой связки опус-
каются внешние скобки у той из двух форм, соединяемых этим вхождением, которая
стоит слева. Например
формула (((А→В)→С→D) может быть записана А→В→С→D.
В-третьих, договоримся считать связки упорядоченными следующим образом: ⎤, &,
∨ , →, ↔ и будем опускать в каждой пропозиционной форме те пары скобок, однознач-
ное восстановление которых возможно на основе следующего правила: пропозицион-
ная формула анализируется на вхождение связок в указанном порядке (т.е. ⎤, &,
∨ , →,
↔). При этом считается, что каждое вхождение ⎤ относится к наименьшей пропозици-
онной форме, следующей за ним (т.е. за ⎤). После расстановки скобок относящихся к
знаку ⎤, анализируются знаки &,
∨ и т.д., причём считаем, что каждая из этих бинар-
ных связок связывает наименьшие формы, окружающие это вхождение (с учётом уже
расставленных скобок).
Например: А→В↔⎤А
∨ В. Здесь скобки восстанавливаются так:
А→В↔(⎤А)
∨ В
А→В↔((⎤А)
∨ В)
(А→В)↔((⎤А)
∨ В)
Лекция №2.
Рассмотрим теперь основные свойства пропозиционных связок. Эти свойства фор-
мируются в виде следующей теоремы:
Т
Т
е
е
о
о
р
р
е
е
м
м
а
а
.
. Пусть А, В, С пропозиционные формы. Тогда следующие формы являют-
ся тавтологиями или тождественно истинными формами:
⎤⎤
А
↔
А (инволюция или закон двойного отрицания)
(2.1)
⎩
⎨
⎧
↔∨
↔&
AAA
AAA
(идемпотентность или законы повторяемости для
&
и
∨
)
(2.2)
⎩
⎨
⎧
∨↔∨
&↔&
ABBA
ABBA
(коммутативность или переместительные законы для
&
и ∨ )
(2.3)
⎩
⎨
⎧
∨∨↔∨∨
&&↔&&
)CB(ACBA
)CB(ACBA
(ассоциативность или сочетательные законы для
&
и
∨
)
(2.4)
⎩
⎨
⎧
∨&∨↔&∨
&∨&↔∨&
)CA()BA(CBA
CABA)CB(A
(дистрибутивность или переместительные законы для
&
и∨ )
(2.5)

Страницы