1 - Алгебра высказываний. Введение. Алгебра логики. Тавтологии и эквивалентность формул. Функции алгебры логики (Конспект лекций), страница 3

Кроме того, исходные значения, по которым отображениеформирует значение, должны быть упорядочены. Одна и та же формула задает разные функции. Так, формула x − t определяет и функцию f (x, t), и функцию f (t, x), а также, например,функцию f (x, y, t). Чтобы с формулой связать некоторую функцию n аргументов, необходимо установить связь между аргументами функции и переменными формулы.

Это в языкахпрограммирования реализуется формальными переменными: f (x, t) = x − t.ÌÃÒÓÔÍ-12формулы. Позже мы увидим, что любая двузначная (булева) функция от n аргументов естьистинностная функция некоторой пропозициональной формулы с n переменными.ÌÃÒÓÔÍ-12ÌÃÒÓ5ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. АЛГЕБРА ВЫСКАЗЫВАНИЙÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓ6Пример 1.1. Формула (x ∨ (¬y)) → z является одновременно выполнимой и опровержимой:она истинна, если переменная z обозначает истинное высказывание, и ложна, если, например,переменные y и z обозначают ложные высказывания. Это можно увидеть, составив истинностную функцию, которая в данном случае описывается вектором 01110101. Формула (x ∨ (¬x))является тавтологией, а формула (x ∧ (¬x)) — противоречием.

#ÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. АЛГЕБРА ВЫСКАЗЫВАНИЙÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12Как и в булевой алгебре, введем понятие эквивалентных формул алгебры высказываний —формул, имеющих равные истинностные значения при любых значениях входящих в формулы переменных. Альтернативное определение: формулы X и Y называются эквивалентными,если формула X ∼ Y является тавтологией.

Нетрудно показать, рассуждая как в последнейтеореме, что формула X ∼ Y является тавтологией тогда и только тогда, когда при любыхзначениях переменных формулы X и Y одновременно или истинны, или ложны, т.е. истинностные функции этих формул совпадают. Для эквивалентных формул введем обозначение X ≡ Y .Итак, X ≡ Y ⇔ X ∼ Y — тавтология. Обратите внимание на три символа эквивалентности в последней фразе.

Первый обозначает отношение эквивалентности формул, введенное намножестве формул алгебры высказываний, третий — операцию эквиваленции, а второй — посути та же эквиваленция, но в утверждении, в котором формулируется свойство самой алгебрывысказываний, и ее следует отнести к сфере метаязыка.Имеются некоторые стандартные приемы, приводящие к эквивалентным формулам. Одиниз них — подстановка. Если мы в формуле заменим одну из подформул другой, то получимновую цепочку символов. Нетрудно доказать индукцией по построению, что это цепочка будетформулой.

Заменяемая подформула может встречаться несколько раз. В этом случае говорято вхождениях подформулы. Замена может выполняться для одного какого-либо вхожденияданной подформулы или для всех.Под подстановкой будем понимать замену всех вхождений в формулу одной или несколькихпеременных некоторыми формулами. Результат подстановки в формулу X вместо переменныхz1 , . . . , zn формул Y1 , . . . , Yn обозначают примерно так: S(z1 , .

. . , zn |Y1 , . . . , Yn |X). Мы такжеnбудем использовать обозначение XYz11 ,...,z,...,Yn .Отметим, что замена в формуле X одного или нескольких вхождений подформулы Y форe подмулой Z можно рассматривать как получение самой формулы X и результата замены Xbстановкой в третью формулу X вместо некоторой переменной u формул Y (для получения X) иe Какие именно вхождения Y меняются, определяется конструкцией форZ (для получения X).b Например, в формуле X = (x → y) ∨ (x ∧ (x ∨ y)) два вхождения формулы Y = x → y.мулы X.Взяв Zb = u ∨ (x ∧ (x ∨ y)), в результате подстановки ZbYu получим X, а в результате подстановкиue = (x ∼ y) ∨ (x ∧ (x ∨ y)) — результат замены в X первого вхожденияZbx∼yполучим формулу XY на формулу Z = x ∼ y.Введем также обозначение X[x1 , x2 , . .

. , xn ], имея в виду, что список x1 , x2 , . . . , xn содержитвсе переменные, входящие в формулу X.ÌÃÒÓÌÃÒÓJ Пусть формулы X и Y построены из переменных z1 , . . . , zn . Выберем для этих переменныхкакие-либо значения. Тогда об истинности формулы X → Y можно судить на основании истинности формул X и Y . Анализируя истинностную функцию для импликации, видим, что приистинности X и ложности Y формула X → Y является ложной.

Но по условию теоремы этаформула тождественно истинная, как и формула X. Следовательно, формула Y не может бытьложной при выбранных значениях переменных. Поскольку значения переменных выбиралисьпроизвольно, заключаем, что формула Y тождественно истинна, т.е. тавтология. IÔÍ-12ÔÍ-12Теорема 1.1. Если формулы X и X → Y являются тавтологиями, то и формула Y естьтавтология.ÌÃÒÓÌÃÒÓСледующее утверждение отражает часто используемое на практике умозаключение, называемое modus ponens (модус поненс).ÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓ7Теорема 1.2. Если X ≡ Y , то при замене всех вхождений какой-либо переменной u и вформуле X, и в формуле Y какой-либо формулой Z получим эквивалентные формулы, т.е.X≡Y⇒XZu ≡ YZu .Если в формуле X заменить одно из вхождений подформулы Y эквивалентной формулой Z, тополучим формулу, эквивалентную X, т.е.Y ≡Z⇒X ≡ XZY .J Объединим списки переменных у формул X, Y , Z в общий упорядоченный список z1 , z2 , .

. . ,zk , u. Тогда условие эквивалентности X ≡ Y можно записать как равенство истинностныхфункций:fX (z1 , . . . , zk , u) = fY (z1 , . . . , zk , u).(1.1)fXe (z1 , . . . , zk , u) = fX (z1 , . . . , zk , fZ (z1 , . . . , zk , u))(1.2)fYe (z1 , . . . , zk , u) = fY (z1 , . . . , zk , fZ (z1 , .

. . , zk , u))(1.3)иÔÍ-12Замена всех вхождений переменной u формулой Z приводит к композиции истинностных функe = X u , Ye = Y u , тоций: если XZZÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. АЛГЕБРА ВЫСКАЗЫВАНИЙe и Ye .а это равносильно эквивалентности формул XПусть дана формула X[x1 , . . . , xn ], в которую входит подформула Y [x1 , . .

. , xn ] (мы можемсчитать, что подформула включает все переменные исходной формулы, рассматривая недостающие как фиктивные). Заменим подформулу Y новой переменной z, которая не входит всписок x1 , . . . , xn . Получим новуюz формулу Γ[x1 , . . . , xn , z], связь которой с исходной формулойможно записать в виде X = ΓY . Замена подформулы Y [x1 , . . . , xn ] эквивалентной формулойe = Γ z .Z[x1 , .

. . , xn ] приведет к новой формуле XZЗадав упорядоченный список переменных x1 , x2 , . . . , xn , z, можем для формул рассмотретьих истинностные функции. По условию fY (x1 , x2 , . . . , xn ) = fZ (x1 , x2 , . . . , xn ) (так как Y ≡ Z),Подстановки вместо z формул Y и Z можно записать как композицию функций:ÔÍ-12ÔÍ-12fXe (z1 , . . .

, zk , u) = fYe (z1 , . . . , zk , u),ÌÃÒÓÌÃÒÓИз равенств (1.1)–(1.3) вытекает, чтоИз равенства fY (x1 , x2 , . . . , xn ) = fZ (x1 , x2 , . . . , xn ) вытекает равенство fX (x1 , x2 , . . . , xn ) =e I= fXe (x1 , x2 , . . . , xn ), что равносильно эквивалентности X ≡ X.Следствие 1.1. Если X — тавтология, то и S(z1 , . . . , zn |Y1 , . . . , Yn |X) — тавтология.J Можно рассуждать так. Тавтологии — это формулы, эквивалентные, например, формулеW = x ∨ ¬x.

В качестве переменной x можно выбрать ту, которая не входит в формулу X. Всилу теоремы, заменив в формулах X и W все вхождения переменных z1 , . . . , zn формуламиY1 , . . . , Yn , мы получим эквивалентные формулы. Но формула W при этом не изменится.Поэтому вновь построенная формула S(z1 , . . . , zn |Y1 , . . . , Yn |X) будет эквивалентна формуле W ,т.е. будет являться тавтологией.

IСледствие 1.2. Пусть X ≡ Z и Y ≡ W . Тогда (X ∨ Y ) ≡ (Z ∨ W ), (X ∧ Y ) ≡ (Z ∧ W ),(X → Y ) ≡ (Z → W ), (X ∼ Y ) ≡ (Z ∼ W ), (¬X) ≡ (¬Z).ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12fXe (x1 , x2 , . . . , xn ) = fΓ (x1 , x2 , . . . , xn , fZ (x1 , x2 , . . . , xn )).ÌÃÒÓÌÃÒÓfX (x1 , x2 , . . . , xn ) = fΓ (x1 , x2 , . . . , xn , fY (x1 , x2 , . . . , xn )),ÌÃÒÓЕще один способ получения эквивалентностей — замена одних операций другими по соответствующим формулам.

Из теории булевых функций вытекает, что верны следующиеэквивалентности:(¬(¬x)) ≡ x,(¬(x ∨ y)) ≡ (¬x) ∧ (¬y),(x → y) ≡ ((¬x) ∨ y).Отталкиваясь от этих эквивалентностей можно доказать следующее.J Доказывается теорема так же, как и предыдущая. Например, на основании простой эквивалентности (¬(¬x)) ≡ x, устанавливаемой непосредственно, путем подстановки вместо переменной x формулы X получаем эквивалентность (¬(¬X)) ≡ X. I¬(x ∨ y) ≡ ¬x ∧ ¬y,¬(x ∧ y) ≡ ¬x ∨ ¬y,t1 ,...,tnX ∗ ≡ ¬X¬t,1 ,...,¬tn(1.4)(1.5)t1 ,...,tn¬Z¬t≡ Z ∗,1 ,...,¬tnÔÍ-12где t1 , t2 , .

. . , tn — полный список переменных, входящих в X. Доказательство проводитсяиндукцией по построению формулы. Действительно, для переменных утверждение очевидно.Пусть X = Y ∨ Z. Тогда, согласно первой эквивалентности (1.4) ¬X = ¬(Y ∨ Z) ≡ ¬Y ∧ ¬Z.Предполагая в соответствии с индуктивным предположением, чтоt1 ,...,tn¬Y¬t≡ Y ∗,1 ,...,¬tnÌÃÒÓДля формул, содержащих только три операции ¬, ∨, ∧, имеет место принцип двойственности. Для каждой такой формулы X в результате взаимной замены операций ∨ и ∧ получимновую формулу X ∗ , которую назовем двойственной для X. Отметим, что если X ∗ двойственна X, то X двойственна X ∗ , так что отношение двойственности симметрично. Это можновыразить формулой X ∗∗ = X (знак равенства отражает совпадение формул, а не их эквивалентность).

Учитывая эквивалентностиÔÍ-12Теорема 1.4. Для любых пропозициональных формул 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ÌÃÒÓÌÃÒÓJ Непосредственно из таблицы для истинностной функции вытекает, что x ∧ x ≡ x.