ДМ_Конспект

Рассматривая конструкции естественного языка, видим, что простые предложения объединяются в сложные при помощи соответствующих сентенциональных связок (союзов), т.е. сложные предложения состоят из простых предложений и служебных слов («если», «то», «и», «или» и т.п.).

Пример.

Составные (сложные) высказывания:

а) «Снег белый, и температура ниже нуля». б) «Если Петр на занятиях, то Аня дома». в) «Петр − студент института или шахтер».

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

Из одних высказываний различными способами можно строить новые, более сложные высказывания, называемые формулами или молекулами, используя те же операции (и их символы), что и в булевой алгебре. Примеры связок и их символов приведены в табл. 10.1.

Таблица 10.1 − Логические связки в логике высказываний

Название	Обозначение				Аналоги естественного языка
Отрицание					не, «неверно, что»
	,
Конъюнкция	,			&	и
Дизъюнкция					или, «или одно из двух …, или оба», либо
Импликация	,				влечет, «если, …то», «только если»,
					«только тогда, когда», «есть
					достаточное условие», «при условии,
					что», «есть необходимое условие»
Эквивалентность	~ , ,				эквивалентно, равносильно, «тогда и
					только тогда, когда», «если и только
					если», «есть необходимое и
					достаточное условие»

Рассмотрим примеры и выражения естественного языка, которые соответствуют логическим связкам.

Определение.

Отрицанием высказывания A называется высказывание (обозначениеA ), которое истинно тогда и только тогда, когда A ложно.

111

Данная унарная операция соответствует отрицанию в естественном языке, которое может иметь различные синтаксические выражения (см. таблицу 4.1).

Пример.

Пусть имеем высказывание A − «Владимир получил электронное письмо от Александра». Отрицанием высказывания A является: A − «Владимир не получил электронное письмо от Александра». Данное высказывание можно представить следующим образом: A − «Неверно, что Владимир получил электронное письмо от Александра».

Определение.

Высказывание A B , называемое конъюнкцией A и B , истинно тогда и только тогда, когда истинны оба высказывания A и B .

Эта логическая операция соответствует в естественном языке связке «и», соединяющей два предложения.

Пример.

Пусть имеем простые высказывания: A − «Харьков является первой столицей Украины»; B − «Харьков − красивый город».

Составное высказывание, определяющее конъюнкцию, будет иметь вид: A B − «Харьков является первой столицей Украины и Харьков − красивый город».

Определение.

Высказывание A B , называемое дизъюнкцией A и B , ложно тогда и только тогда, когда ложны оба высказывания A и B .

Эта логическая операция соответствует соединению высказываний естественного языка с помощью связки «или», употребляемой в смысле «не исключающее или»: «верно» A , или верно B , или оба высказывания равны.

Пример. Пусть имеем два атома: A − «5 2 10» и B − «5 2 10 ». Тогда высказывание «5 2 10 или 5 2 10 » будет соответствовать формуле A B .

Определение.
Высказывание	A B ,	называемое	импликацией	(условным

предложением), ложно тогда и только тогда, когда A истинно, а B ложно.

В импликации A B высказывание A называется посылкой (условием,

антецедентом), а B следствием (заключением, консеквентом).

Выражаемая импликацией причинно-следственная связь между A и B на естественном языке описывается следующими оборотами: « A влечет B », «если A , то B », « A является достаточным основанием для B », « B , потому что A », « B при условии выполнения A ». Используемые в точных науках понятия достаточного и необходимого условий можно формально выразить с помощью импликации.

Пример.

Пусть имеем два атома: A − « x − простое» и B − « x − нечетное». Тогда высказывание «Для того, чтобы x было нечетным, достаточно, чтобы x было простым» будет соответствовать формуле A B .

Определение.

112

Определение.

Логика высказываний

Если A и B высказывания, то высказывание A ~ B , называемое эквиваленцией, истинно тогда и только тогда, когда A и B либо оба истинны, либо оба ложны.

Эта операция в естественном языке соответствует оборотам: «… тогда и только тогда, когда …», «для того чтобы …, необходимо и достаточно …»,

Пример.

Пусть имеем два атома: A − «идет дождь» и B − «на небе тучи». Тогда высказывание «Дождь идет тогда и только тогда, когда на небе тучи» будет соответствовать формуле A ~ B .

Алфавит логики высказываний содержит следующие символы:

1)высказывательные переменные A, B, C, ... или заглавные буквы с

индексами;

2)логические символы (связки) , , , , ~ ;

3)символы скобок ( ) и запятую.

Связки могут быть бинарными и унарными. Операции , , , ~

являются бинарными логическими связками, операция − унарной логической связкой.

При записи формул можно обойтись без некоторых скобок, если приписать ранги логическим связкам. Ранги логических связок чаще всего задаются в таком порядке (от высшего к низшему): , , , , ~ .

Пример. P − «Влажность большая»; Q − «Температура высокая»; C −

«Мы чувствуем себя хорошо».

Высказывание «Если влажность большая и температура высокая, то мы не чувствуем себя хорошо» можно записать в виде формулы ((P Q) (C))

или с учетом рангов операций P Q C .

Определение. В логике высказываний правильно построенная формула

определяется рекурсивно следующим образом: 1. Атом есть формула.

2. Если A и B формулы, то (A B), (A B), (A B), (A ~ B), A

также формулы.

3. Никаких формул, кроме порожденных указанными выше правилами, не существует.

10.3 Алгебра логики и логика высказываний

– это алгебраическая структура ({Л, И}, , , , , ~,) ) с носителем – двоичным множеством { Л : «Ложь», И :

«Истина»}, операциями (логическими связками): « » – конъюнкция, « » – дизъюнкция, « » – отрицание, « » – импликация, «~» – эквивалентность.

113

Если рассмотреть две алгебры:	алгебру логики A1 ({0,1}, , , , , ~) и
алгебру логики высказываний A2	({Л, И},,, , , ~), то они будут

изоморфны друг другу, так как можно поставить взаимно однозначное соответствие между множествами 0 Л , 1 И , а операции просто одинаковы. Если алгебры изоморфны, то элементы и операции A2 можно переименовать так, что A2 совпадает с A1 . Из условия изоморфности следует, что любое эквивалентное соответствие в алгебре A1 сохраняется в A2 . То есть соотношения, полученные в алгебре A1 , автоматически распространяются на алгебру A2 .

Слогической точки зрения двоичные объекты, которые рассматривались

вразделе «Элементы математической логики. Алгебра булевых функций», это высказывания, которые могут быть истинными или ложными. Формулы это составные высказывания, истинность которых определяется истинностью входящих в них элементарных высказываний (обозначаемых буквами) и логическими операциями над высказываниями.

Поэтому все утверждения относительно алгебры логики справедливы и для алгебры логики высказываний.

Если рассматривать формулы, содержащие только логические операции , , , то в логике высказываний выполняется закон двойственности. Кроме

того, формулы логики высказываний можно представить в виде ДНФ и КНФ, СДНФ и СКНФ (учитывая изоморфизм алгебр).

10.4 Интерпретация формул логики высказываний. Правильные

рассуждения

Определение.

Приписывание истинностных значений атомам, из которых построено высказывание, называется интерпретацией высказывания.

Для высказывания, содержащего n атомов, можно составить 2n интерпретаций, так же, как и для n -местной булевой функции.

Формулы логики высказываний можно задавать таблицами истинности, подобно булевым функциям.

Пример.

Рассмотрим таблицу истинности для логических связок логики высказываний (таблица 10.2)

Таблица 10.2 Таблица истинности логических связок

A	B				A B	A B	A B	A ~ B
			A
Л	Л	И			Л	Л	И	И
Л	И	И			Л	И	И	Л
					114

И	Л	Л	Л	И	Л	Л
И	И	Л	И	И	И	И

Исходя из принимаемых формулами логики высказываний истинностных значений, формулы разделяются на тождественно истинные, тождественно ложные и необщезначимые.

Определение.

Формула называется тождественно истинной (тавтологией или

общезначимой), если она принимает значение «истина» на всех интерпретациях (наборах значений переменных).

Определение.

Формула называется тождественно ложной (противоречивой или

невыполнимой), если она принимает значение «ложь» на всех интерпретациях.

Определение.

Формула называется необщезначимой или непротиворечивой, если она на одних интерпретациях принимает значение «истина», а на других – «ложь».

Определение.

Все формулы, не относящиеся к противоречивым, образуют множество

выполнимых формул.

Пример.

Формула	A A	− тавтология; формула A A	является
противоречивой; формула A A является выполнимой.
Перечислим	наиболее	важные тавтологии, предполагая, что	A, B,C −

произвольные формулы:

1.A A ;

2.A A ;

3.A (B A) ;

4.(A B) ((B C) (A C));

5.(A (B C)) ((A B) (A C)) ;

6. (A B) A,		(A B) B ;
7.	A (B ( A B));
8.	A (A B),	B (A B) ;

9.(B A) ((B A) B) ;

10.((A B) A) A (закон Пирса).

При доказательстве утверждений различных математических теорий обычно используют рассуждения, которые на языке логики можно выразить формулами.

Определение.

Рассуждение называется правильным, если оно выражается тождественно истинной формулой.

115

Таким образом, проверить правильность рассуждения можно, построив соответствующую ему формулу и определив, является ли она тождественно истинной.

Доказать, что формула является тавтологией, можно следующими способами:

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

2.Применив тождественные преобразования, привести еѐ к виду одного из логических законов. Если в результате преобразований получим значение «истина», то формула является тавтологией.

10.5 Логическая эквивалентность и логическое следствие

Определение.

Две формулы называются равносильными, если на всех наборах значений входящих в них переменных эти формулы принимают одинаковые значения.

Равносильность формул логики высказываний вытекает из тождественности соответствующих формул алгебры логики. Равносильности формул A и B будем обозначать через A B . Легко видеть, что равносильность − это отношение эквивалентности (оно рефлексивно, симметрично и транзитивно), поэтому равносильность называют также

логической эквивалентностью.

Теорема.

Если A, B,C − любые формулы, то имеют место следующие логические эквивалентности:

1.A B B A, A B B A (коммутативность).

2.A (B C) (A B) C , A (B C) (A B) C (ассоциативность).

3.A (B C) (A B) (A C) ,

A (B C) (A B) (A C) (дистирибутивность).

4.A A A, A A A (идемпотентность).

5.A ( A B) A, A ( A B) A (законы поглощения).

6.A A (закон двойного отрицания.)

7.(A B) A B , (A B) A B (законы де Моргана).

8.A Л А, A Л Л .

9.A И И , A И А.

10.A А И , A А Л .

Кроме того, с помощью отношения равносильности выражаются

различные

связки

между

формулами:

A B A B ,

A ~ B AB AB ( A B)(A B),

A B A B ,

AB A B ,

A ~ B (A B)(B A) , A ( A B) (A B) , A ( A B) (A B) . 116

Любая из равносильностей может быть доказана с помощью таблиц истинности (а также следует из изоморфизма алгебр A1 и A2 ).

Рассмотренные и подобные им равносильные соотношения можно использовать для преобразования и упрощения структуры сложного высказывания.

Определение. Высказывание B является логическим следствием высказывания A , если формула A B является тождественно истинной.

Данное определение может быть обобщено на случай произвольного числа посылок.

Определение. Высказывание B является логическим следствием высказываний A1 , A2 ,..., An , если A1 A2 ... An B − тождественно истинная

формула.

Пример. Показать, что высказывание ( A B) C является логическим

следованием высказывания A C .

Покажем, что формула (A C) (A B) C является общезначимой. Для этого используем тождества логики высказываний для эквивалентных

преобразований, учитывая, что x y f13 (x, y) x y :

(A C) (A B) C (A C) (A B) C A C (A B) CA (A B) C C A ( A B) И И .

Общезначимость формулы доказана.

10.6 Контрольные вопросы и задания

1.Какой вид предложений моделирует формальная логика?

2.Дайте определение понятию высказывание.

3.Дайте определение понятию алгебры логики высказываний.

4.Какие высказывания называются атомами?

5.Что в логике высказываний называют логическими связками?

6.Что в логике высказываний называют молекулами?

7.Дайте характеристику алфавита логики высказываний.

8.Что подразумевают в логике высказываний под правильно построенной формулой?

9.Дайте определение логического следствия одного (нескольких) высказываний.

10.Покажите, что алгебра логики и логика высказываний являются изоморфными.

11.Какие формулы можно получить, исходя из принимаемых формулами логики высказываний истинностных значений?

12.Какое рассуждение называется правильным?

13.Перечислите наиболее важные тавтологии.

14.Какие формулы называются равносильными? Приведите примеры равносильных формул.

117

ЛЕКЦИЯ 11. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

11.1 Основные понятия исчисления высказываний

Рассмотренное содержательное описание логики высказываний позволяет ответить на многие вопросы данной логики (например, является ли формула тавтологией, равносильны ли две заданные формулы и т.д.), используя таблицы истинности либо эквивалентные преобразования формул. Однако для ответа на более сложные вопросы используется другой метод − метод формальных

аксиоматических теорий.
Исчисление	высказываний,	являясь	формальной системой,

представляет собой пример аксиоматической теории и один из возможных способов формализации логики высказываний. В исчислении высказываний особое внимание уделяется тождественно истинным высказываниям, поскольку они должны входить в любую теорию в качестве общелогических законов. Их порождение и является основной задачей исчисления высказываний. Данная формальная система позволяет проверить, является ли заданная формула тавтологией, а также получить общезначимые формулы логики высказываний.

Исчисление высказываний содержит язык, систему аксиом и правила вывода.

Рассмотрим каждое из этих составляющих.

Определение. Язык исчисления высказываний, являясь формальным языком для математических рассуждений, состоит из формул логики высказываний, правильно построенных с использованием алфавита данной логики.

Пример. Правильно построенные формулы с использованием алфавита логики высказываний: ((A (A B)) ((C D) (A B))),

(A (B (C D))). Выражения, не являющиеся формулами: ( A B , A B , A. 11.2 Аксиомы и полнота исчисления логики высказываний

В математике и «чистой» логике доказывают теоремы, т.е. выводят следствия из определенных допущений, которые называются аксиомами или гипотезами. При этом предполагается, что они (аксиомы или гипотезы) тождественно истинны во всей рассматриваемой теории.

Определение.

Аксиомами логики высказываний является некоторое множество общезначимых формул логики высказываний.

Аксиомы (гипотезы) представляют собой перечень одного или более высказываний (посылок), которые часто называются схемами аксиом.

118

Системы аксиом исчисления высказываний подбираются таким образом, чтобы исчисление обладало свойством полноты.

Полнота исчисления высказываний заключается в том, что в данной системе имеется достаточное количество аксиом для того, чтобы вывести любую формулу логики высказываний, которая является тождественно истинной.

11.3 Выводимость в исчислении высказываний

Определение.

Выводом в исчислении высказывания называется всякая последовательность A1 , A2 ,..., An формул такая, что для любого i формула Ai

есть либо аксиома, исчисления высказываний, либо непосредственное следствие каких-либо предыдущих формул, полученных по правилу вывода.

Определение.

Формула A называется теоремой исчисления высказывания (как аксиоматической теории), если в ней существует вывод, в котором последней формулой является A . Этот вывод называется выводом формулы A .

Определение.

Формула A называется следствием множества формул G тогда и только тогда, когда существует такая последовательность формул A1 , A2 ,..., An ,

что An есть A , и для любого i формула Ai есть либо аксиома, либо формула из

G , либо непосредственное следование некоторых предыдущих формул. Эта последовательность называется выводом A из G . Элементы G называются

посылками вывода или гипотезами.

Сокращенно можно записать так: G A ( A есть следствие G ). Если множество G состоит из формул B1 , B2 ,...,Bk , то пишут B1 , B2 ,...,Bk A.

Правила вывода позволяют получать новые формулы, которые являются истинными при условии истинности всех посылок, входящих в правило.

В логике правила вывода используются, чтобы выводить одни истинные предложения из других истинных предложений.

Доказательство в исчислении высказываний представляет собой логический вывод списка высказываний.

Определение.

Дедуктивным выводом называется вывод формулы B из формулы A , основанный на том, что B является логическим следствием A .

Правила для дедуктивного вывода строятся на основе общезначимых формул логики высказываний вида A B . Эти правила часто записывают как

правила формального вывода в следующем виде A1 , A2 ,...,A , где A1, A2 ,...,A B

посылки вывода, а B следствие (заключение). Тавтология, соответствующая такому правилу, это A1 A2 ... An B .

119

	Пример.
	Рассуждение по схеме	A B, B	не правильное рассуждение, так как
		A

формула ((A B) B) A не является тавтологией. Например, пусть A : «5 −

простое число» и B : «5 − нечетное число», A B : «Если 5 − простое число, то 5 − нечетное число» и B : «5 − нечетное число», то A : «5 − простое число», не правильное рассуждение.

Наиболее часто в практических задачах используются: а) правило отделения; б) правило подстановки.

Правило отделения имеет следующий логический смысл: если посылка верна, то верно и следствие из неѐ.

Пример.

Рассуждения с помощью правила отделения:

«Если студент не выучил теорию, то он не выполнит задание. Студент не выучил теорию. Следовательно, студент не выполнит задание».

«Если студент получил пять, значит, он решил задачу. Студент получил пять. Следовательно студент решил задачу».

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

Рассмотрим правило подстановки. Пусть F1 и F2 − формулы логики высказываний, A − атомарная формула. Если F1 ( A) − формула, выводимая в исчислении высказываний, содержащая атом A , то F1 (B) − выводимая формула, полученная заменой всех вхождений A в формуле F1 на формулу F2 .

Правило подстановки записывается следующим образом:				F1 ( A || F2 )	.
				F1 (B)
Пример.
Используя правило подстановки и коммутативный закон для
дизъюнкции,	доказать	общезначимость	следующей			формулы:

A B C ~ B C A.

Запишем тождество, соответствующее коммутативному закону длдя

дизъюнкции:	A D ~ D A . Определим подстановку − атомарную формулу D
заменим на	B C :	A (B C) ~ (B C) A . Если опустить скобки в

соответствии с приоритетом операций, то можно убедиться в истинности исходной формулы.

Кроме рассмотренных правил вывода в исчислении высказываний часто используются правила дедуктивного вывода, представленные в табл. 11.1.

120