2 - Логика высказываний. Алгебра высказываний. Тавтологии и эквивалентность формул. Способы получения эквивалентных формул (Конспект лекций)

Московский государственный технический университетимени Н.Э. БауманаÌÃÒÓФакультет «Фундаментальные науки»Кафедра «Математическое моделирование»À.Í. ÊàíàòíèêîâÄÈÑÊÐÅÒÍÀßÌÀÒÅÌÀÒÈÊÀÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÊîíñïåêò ëåêöèéÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÄëÿ ñòóäåíòîâ ñïåöèàëüíîñòè<Ïðèêëàäíàÿ ìàòåìàòèêà>ÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12Москва2006ÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓ2. ЛОГИКА ВЫСКАЗЫВАНИЙÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-1218ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12Напомню, что под высказыванием понимается любое предложение, относительно которогоможно сказать истинно оно или нет, т.е.

утвердительное предложение. Строго говоря, сказанноене следует рассматривать как настоящее математическое определение — лишь как указание нате реальные объекты, которые могут служить иллюстрацией к точной математической теории.Формирование предложений в естественном языке указывает на то, что высказывания могутобъединяться с помощью связывающих союзов. С математической точки зрения эти союзыреализуют операции над высказываниями. Выделим пять таких операций:1) дизъюнкция (соответствует союзу или“);”2) конъюнкция (соответствует союзу и“);”3) импликация (соответствует фразе типа если . .

. , то );””4) эквиваленция (соответствует фразе типа . . . тогда и только тогда, когда . . . );”5) отрицание (соответствует союзу не“).”Первые четыре из этих операций бинарные, последняя унарная. Относительно указанныхопераций можно сказать лишь, что они формируют новое высказывание. При этом, зная, истинны или ложны исходные высказывания, можно сказать, является ли истинным вновь образованное высказывание.

Введенные пять операций мы будем называть логическими или пропозициональными.Мы имеем дело с некоторой алгебраической системой, и для нее можно ввести свой математический язык — язык алгебры высказываний. В этом языке из заданного набора символов —алфавита языка — по определенным правилам составляются последовательности, называемыесловами или фразами, формулами.Алфавит языка алгебры высказываний составляют множество пропозициональных переменных, множество функциональных символов (символов операций, или логических связок) ∨, ∧, →, ∼, ¬ и множество служебных символов (две круглые скобки).

Формулы языкавводятся индуктивно.База индукции: пропозициональные переменные представляют собой формулы.Шаг индукции: если X и Y — формулы, то формулами являются (X ∨ Y ), (X ∧ Y ), (X → Y ),(X ∼ Y ), (¬X).Договоримся о следующих обозначениях. Будем обозначать: пропозициональные переменные — строчными латинскими буквами конца алфавита (x, y, z и т.д.); какие-либо формулы —прописными латинскими буквами конца алфавита (X, Y , Z и т.д.). Как и в теории булевыхфункций, для сокращения количества скобок в формулах договоримся о таком же приоритетеопераций. Это соглашение не относится к самому языку ми служит лишь для удобства.В наших рассуждениях будут встречаться формулы, которые относятся к введенному языку,но, кроме того, придется использовать и дополнительные обозначения и символику, чтобы рассуждать не в рамках языка, а о самом языке и его формулах.

Так, обозначения переменных —это элемент языка алгебры высказываний, а обозначения формул уже выходят за рамки языка.ÌÃÒÓÌÃÒÓВысказывания и их истинностные значения. Логические операции ∨, ∧, →, ∼, ¬. Пропозициональные операции и связки. Пропозициональные формулы: пропозициональные переменныеи шаг индукции (X ∨ Y , X ∧ Y , X → Y , ¬X).

Язык и метаязык. Истинностные функции ипропозициональные формулы. Утверждение: каждая истинностная функция соответствуетнекоторой пропозициональной формуле.ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓ2.1. Алгебра высказыванийÌÃÒÓJ Язык алгебры высказываний совпадает с языком булевой алгебры, построенным на множестве из пяти булевых функций ∨, ∧, →, ∼, ¬. Поскольку это множество содержит стандартныйбазис в B и, следовательно, полно, любая булева функция может быть представлена формулойнад заданным множеством. Эту формулу можно рассматривать как формулу алгебры высказываний. При этом булева функция будет истинностной функцией указанной формулы.

IÔÍ-122.2. Тавтологии и эквивалентность формулТавтологии. Формулы выполнимые и опровержимые. Теорема о правиле modus ponens: ЕслиX и X →Y — тавтологии, то и Y — тавтология. Подстановка S(z1 , z2 , . . . , zn |Y1 , Y2 , . . . , Yn |X)(результат подстановки Yi вместо zi ) — пропозициональная формула. Эквивалентность формул алгебры высказываний. Теорема о заменах.

Следствие 1: если X — тавтология, то иS(z1 , z2 , . . . , zn |Y1 , Y2 , . . . , Yn |X) — тавтология. Следствие 2: инвариантность эквивалентности относительно логических операций.ÌÃÒÓÔÍ-12Среди формул алгебры высказываний выделяют:– выполнимые, имеющие значение 1 хотя бы для одного набора значений пропозициональных переменных;– опровержимые, имеющие значение 0 хотя бы для одного набора значений пропозициональных переменных.Формула, не являющаяся опровержимой, истинна при любом значении переменных. Такуюформулу называют тождественно истинной или тавтологией. Тавтологии описываютуниверсальные логические законы.

Именно с использованием тавтологий проводится любоематематическое доказательство.Формула, не являющаяся выполнимой, ложна при любом значении переменных. Такую формулу называют тождественно ложной или противоречием.Для тавтологий (противоречий) истинностная функция есть константа 1 (0). Для выполнимых формул истинностная функция не равна постоянной 0, а для опровержимых — постоянной 0.ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12Теорема 2.1.

Каждая булева функция является истинностной функцией некоторой формулы алгебры высказываний.ÌÃÒÓÌÃÒÓДополнительное соглашение о приоритете операций также выходит за рамки языка. В этомслучае говорят о расширении рассматриваемого языка или о метаязыке. На практике языки метаязык тесно переплетаются, и разделить их не просто.Слова языка алгебры высказываний, называемые пропозициональными формулами, —лишь цепочки символов, составленные по определенным правилам.

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

Самаподстановка вместо переменных конкретных высказываний уже выходит за рамки рассматриваемого языка. Отметим, что формулы алгебры высказываний имеют и другие интерпретации. Например, пропозициональные переменные можно рассматривать как булевы переменные, а функциональные символы увязать с соответствующими булевыми операциями. Такаяинтерпретация позволяет получить исходя из истинности высказываний истинность сложноговысказывания. Формула будет определять булеву функцию, которую называют истинностной функцией. Именно истинностные функции и следует рассматривать как главную цельизучения в алгебре высказываний, поскольку она позволяет судить об истинности сложных,запутанных высказываний.ÌÃÒÓÔÍ-12ÌÃÒÓ19ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-122.

ЛОГИКА ВЫСКАЗЫВАНИЙÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓ20Пример 2.1. Формула (x ∨ (¬y)) → z является одновременно выполнимой и опровержимой:она истинна, если значением переменной z является истинное высказывание, и ложна, если,например, значениями переменных y и z являются ложные высказывания. Это можно увидетьсоставив истинностную функцию, которая в данном случае описывается вектором 01110101.Формула (x ∨ (¬x)) является тавтологией, а формула (x ∧ (¬x)) — противоречием. #ÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-122. ЛОГИКА ВЫСКАЗЫВАНИЙСледствие 2.1. Если X — тавтология, то и S(z1 , . . . , zn |Y1 , .

. . , Yn |X) — тавтология.J Можно рассуждать так. Тавтологии — это формулы, эквивалентные, например, формулеW = x ∨ ¬x. В качестве переменной x можно выбрать ту, которая не входит в формулу X. Всилу теоремы, заменив в формулах X и W все вхождения переменных z1 , . . . , zn формуламиY1 , . . . , Yn , мы получим эквивалентные формулы.

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

. . , zn |Y1 , . . . , Yn |X).ÌÃÒÓТеорема 2.3. 1) Если X ≡ Y , то при замене всех вхождений какой-либо переменной и в X,и в Y какой-либо формулой Z получим эквивалентные формулы.2) Если в формуле X заменить одно из вхождений подформулы Y эквивалентной формулойZ, то получим формулу, эквивалентную X.ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12Как и в булевой алгебре, введем понятие эквивалентных формул алгебры высказываний —формул, имеющих равные истинностные значения при любых значениях входящих в формулыпеременных. Альтернативное определение: формулы X и Y называются эквивалентными, еслиформула X ∼ Y является тавтологией.

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