2 - Логика высказываний. Алгебра высказываний. Тавтологии и эквивалентность формул. Способы получения эквивалентных формул (1059973), страница 2
Текст из файла (страница 2)
Один из них — подстановка. Если мы в формуле заменимодну из подформул другой, то получим новую цепочку символов. Нетрудно доказать индукциейпо построению, что это цепочка будет формулой. Заменяемая подформула может встречатьсянесколько раз. В этом случае говорят о вхождениях подформулы. Замена может выполняться для одного какого-либо вхождения данной подформулы или для всех.
Из теории булевыхфункций вытекает следующий результат.ÌÃÒÓÌÃÒÓJ Пусть формулы X и Y построены из переменных z1 , . . . , zn . Выберем для этих переменныхкакие-либо значения. Тогда об истинности формулы X → Y можно судить на основании истинности формул X и Y . Анализируя истинностную функцию для импликации, видим, что приистинности X и ложности Y формула X → Y является ложной. Но по условию теоремы этаформула тождественно истинная, как и формула X.
Следовательно, формула Y не может бытьложной при выбранных значениях переменных. Поскольку значения переменных выбиралисьпроизвольно, заключаем, что формула Y тождественно истинна, т.е. тавтология. IÔÍ-12ÔÍ-12Теорема 2.2. Если формулы X и X → Y являются тавтологиями, то и формула Y естьтавтология.ÌÃÒÓÌÃÒÓСледующее утверждение отражает часто используемое на практике умозаключение, называемое modus ponens (модус поненс).ÌÃÒÓ2.3. Способы получения эквивалентных формулЭквивалентности на основе свойств логических операций (коммутативность, ассоциативность, идемпотентность, дистрибутивность, поглощение). Эквивалентности на основе взаимосвязей операций. Эквивалентности на основе двойственностиС помощью подстановки можно получать эквивалентные формулы, отталкиваясь от известных свойств логических операций.Теорема 2.4.
Для любых пропозициональных формул X, Y и Z верны следующие эквивалентности: 1) X ∧ X ≡ X; 2) X ∧ Y ≡ Y ∧ X; 3) (X ∧ Y ) ∧ Z) ≡ (X ∧ (Y ∧ Z); 4) X ∨ X ≡ X;5) X ∨ Y ≡ Y ∨ X; 6) (X ∨ Y ) ∨ Z) ≡ (X ∨ (Y ∨ Z); 7) X ∧ (Y ∨ Z) ≡ (X ∧ Y ) ∨ (X ∧ Z);8) X ∨ (Y ∧ Z) ≡ (X ∨ Y ) ∧ (X ∨ Z); 9) X ∧ (Y ∨ X) ≡ X; 10) X ∨ (Y ∧ X) ≡ X.J Непосредственно из таблицы для истинностной функции вытекает, что x ∧ x ≡ x. Подставив вместо всех вхождений переменной x формулу X, получим эквивалентность X ∧ X ≡ X.Остальные эквивалентности доказываются аналогично.
IОтталкиваясь от этих эквивалентностей можно доказать следующее.Понятие двойственности из теории булевых функций переносится на алгебру высказываний.В данном случае речь идет о формулах, содержащих только базовые операции ∨, ∧, ¬. Длялюбой такой формулы X двойственная формула X ∗ получается взаимной заменой операций∨ и ∧.ÔÍ-12J Доказывается теорема так же, как и предыдущая. Например, на основании простой эквивалентности (¬(¬x)) ≡ x, устанавливаемой непосредственно, путем подстановки вместо переменной x формулы X получаем эквивалентность (¬(¬X)) ≡ X. IÌÃÒÓТеорема 2.5.
Для любых пропозициональных формул X, Y и Z верны следующие эквивалентности:1) (¬(¬X)) ≡ X (закон двойного отрицания);2) (¬(X ∨ Y )) ≡ (¬X) ∧ (¬Y )) (перенос отрицания через конъюнкцию);3) (¬(X ∧ Y )) ≡ (¬X) ∨ (¬Y )) (перенос отрицания через дизъюнкцию);4) (¬(X → Y )) ≡ (X ∧ (¬Y )) (перенос отрицания через импликацию);5) (X → Y ) ≡ ((¬X) ∨ Y ) (представление импликации через дизъюнкцию);6) (X → (¬X)) ≡ (¬X) (закон упрощения);7) (X → Y ) ≡ ((¬Y ) → (¬X) (закон контрапозиции).ÔÍ-12Еще один способ получения эквивалентностей — замена одних операций другими по соответствующим формулам. Из теории булевых функций вытекает, что верны следующие эквивалентности:(¬(¬x)) ≡ x, (¬(x ∨ y)) ≡ (¬x) ∧ (¬y), (x → y) ≡ ((¬x) ∨ y).ÌÃÒÓÔÍ-12ÌÃÒÓJ Формулу (Z ◦ W ), где ◦ — одна из логических связок, можно рассматривать как результатзамены в формуле (X ◦ Y ) сперва подформулы X эквивалентной формулой Z, а затем подформулы Y эквивалентной формулой W .
Согласно доказанной теореме такая замена приводит кэквивалентной формуле. Аналогичны рассуждения и для отрицания. IÔÍ-12ÔÍ-12Следствие 2.2. Пусть X ≡ Z и Y ≡ W . Тогда (X ∨ Y ) ≡ (Z ∨ W ), (X ∧ Y ) ≡ (Z ∧ W ),(X → Y ) ≡ (Z → W ), (X ∼ Y ) ≡ (Z ∼ W ), (¬X) ≡ (¬Z).ÌÃÒÓÌÃÒÓПоэтому вновь построенная формула S(z1 , . . . , zn |Y1 , . . . , Yn |X) будет эквивалентна формуле W ,т.е. будет являться тавтологией. IÌÃÒÓÔÍ-12ÌÃÒÓ21ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-122. ЛОГИКА ВЫСКАЗЫВАНИЙÌÃÒÓÔÍ-12ÌÃÒÓ22Переход к двойственной формуле соответствует переходу от булевой функции f (x) к двойственной функции f (x).
Понятие двойственных функций позволяет ввести понятие двойственности для любых формул алгебры высказываний, однако для произвольных формул двойственность не является такой простой, как в случае трех базовых операций. Из понятия двойственныхфункций вытекает, что двойственность — симметричное отношение, т.е. X ∗∗ = X (здесь знакравенства означает не эквивалентность формул, а их совпадение). Из понятия двойственностифункций вытекает и следующая эквивалентность:ÔÍ-12X ∗∗ ≡ S(t1 , . . . , tn |¬t1 , . . . , ¬tn |¬X),ÌÃÒÓгде t1 , .
. . , tn — полный список переменных формулы X.Каждая булева функция может быть представлена формулой над стандартным базисом. Приэтом булева функция, не равная тождественно 0, может быть представлена совершенной дизъюнктивной нормальной формой, а булева функция, не равная тождественно 1, — совершеннойконъюнктивной нормальной формой. Отсюда вытекает следующее утверждение.ÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12Теорема 2.6. Каждая формула алгебры высказываний, не являющаяся противоречием,имеет эквивалентную ей совершенную ДНФ.
Каждая формула алгебры высказываний, не являющаяся тавтологией, имеет эквивалентную ей совершенную КНФ. #ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-122. ЛОГИКА ВЫСКАЗЫВАНИЙÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÌÃÒÓ3. Исчисление высказываний3.1. Введение . . .
. . . . . . . . . .3.2. Основные положения теории N3.3. Правила естественного вывода3.4. Глобальные свойства теории N....2323242530.......35353639424447495. Исчисление предикатов5.1. Построение теории P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5.2. Правила естественного вывода . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .5.3. Глобальные свойства теории P . . . . . . . . . . . . . . . . . . . . . . . . . . . . .515152546. Алгоритмы на графах6.1. Введение . . . . . . . . . . . . . . . .6.2. Деревья . . . . . . . . . . . . . . . .
.6.3. Остов графа наименьшего веса . . .6.4. Задача о путях в размеченном графе6.5. Циклы, разрезы и задача Эйлера . .555557606266...............................................................................4. Алгебра предикатов4.1. Предикаты и кванторы . . . . . . . . . . .4.2. Логико-математические языки . . . . . . .4.3. Переименования и подстановки . . . . .
.4.4. Семантика логико-математического языка4.5. Логические законы . . . . . . . . . . . . .4.6. Замены . . . . . . . . . . . . . . . . . . . .4.7. Упрощение формул . . . . . . . . . . . . .........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................ÔÍ-12ÔÍ-12..........ÌÃÒÓ18181921.....ÔÍ-122.
Логика высказываний2.1. Алгебра высказываний . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2. Тавтологии и эквивалентность формул . . . . . . . . . . . . . . . . . . . . . . . . .2.3. Способы получения эквивалентных формул . . . . . . . . . . . . . . . . . . . . . ......ÌÃÒÓ.....11291112ÔÍ-1273ÌÃÒÓÔÍ-121. Булевы функции1.1.
Булевы алгебры . .1.2. Булевы функции . .1.3. ДНФ и КНФ . . . .1.4. Критерий Поста . .1.5. Минимизация ДНФÔÍ-12ÌÃÒÓОГЛАВЛЕНИЕÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
