Тема 2. Классическая логика высказываний

Язык логики высказываний. Разрешающие процедуры классической логики высказываний (истинностные таблицы). Алгоритм построения таблиц истинности. Формализация логики высказываний методом аналитических таблиц. Натуральное исчисление высказываний.

Язык логики высказываний. Логика высказываний (пропозициональная логика) – теория, изучающая логическую структуру сложных высказываний, отношения между ними и выводы, построенные на основе этой структуры.

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

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

Алфавит данного языка включает в себя следующие символы:

1. пропозициональные переменные – А, В, С,… (иногда используются иные буквы латинского алфавита, например, p, q, r…)

Пропозициональные переменные замещают собой простые высказывания. Например, высказывание «Сегодня на улице идет дождь» можно обозначить символом А, а высказывание «Сегодня на улице светит солнце» - символом В, и т.д.

2) пропозициональные связки - ¬, ˄, v, v, , ↔.

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

¬ - отрицание («не», «неверно, что» и т.п.)

˄ - конъюнкция («и», «а», «но», «да», «ни, ни» и т.п.)

˅ - нестрогая дизъюнкция («или», «по крайне мере, одно из двух» и т.п.)

˅ - строгая дизъюнкция («либо – либо», «только одно из двух» и т.п.)

 - импликация («если, то», «значит» и т.п.)

↔ - эквиваленция («если и только если», «равнозначно» и т.п.)

2. скобки – ( , ).

Любая последовательность знаков этого алфавита называется выражением языка КЛВ. Некоторые из них являются правильно построенными формулами, если они соответствуют следующему определению:

1. Каждая пропозициональная переменная является формулой.

2. Если А – формула, то ¬А также является формулой.

3. Если А и В – формулы, то выражения (А ˄ В), (А ˅ В), (А ˅ В),

(А  В), (А ↔ В) также являются формулами.

4. Ничто иное не является формулой.

Правильно построенные формулы представляют собой логические формы высказываний естественного языка, записанные на языке КЛВ. Например, пусть А означает «студент хорошо сдаст сессию», В означает «студент будет пересдавать экзамены», С – «у студента будет хорошее настроение». Тогда переводом высказывания «если студент хорошо сдаст сессию, то он не будет пересдавать экзамены и у него будет хорошее настроение» будет формула (А  (¬В ˄ С)). Формула, входящая в состав некоторой формулы, называется ее подформулой и выделяется скобками.

Разрешающие процедуры КЛВ (истинностные таблицы). Каждая логическая теория, в том числе и логика высказываний, решает две основные задачи: во-первых, выявляет класс формул, являющихся логическими законами; во-вторых, устанавливает отношение логического следования между формулами.

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

Определение 2 (логического следование). Заключение логически следует из множества посылок, если и только если логическая форма данного рассуждения гарантирует, что при истинности посылок заключение тоже всегда будет истинным.

Определение 3 (разрешимости логической теории). Логическая теория называется разрешимой, если существует эффективная процедура (алгоритм), позволяющая для любой формулы языка теории в конечное число шагов определить, является ли эта формула логическим законом или нет.

Классическая логика высказываний является разрешимой теорией и для нее существует несколько разрешающих процедур. Одну из них представляет табличный способ определения истинностных значений формул.

Каждая отдельная пропозициональная переменная, замещающая собой простое высказывание, может быть истинной или ложной. Это обозначается, соответственно, (1) и (0). Истинность или ложность сложных формул зависит от истинностных значений входящих в них переменных. Эта зависимость представлена в следующей таблице:

А	В	А ˄ В	А ˅ В	А ˅ В	А  В	А ↔ В			А	¬А
1	1	1	1	0	1	1			1	0
1	0	0	1	1	0	0			0	1
0	1	0	1	1	1	0
0	0	0	0	0	1	1

Алгоритм построения таблицы истинности.

1. Определить число строк в таблице, используя формулу k = 2ⁿ, где k – число строк в таблице, а n – число пропозициональных переменных, входящих в формулу.

2. Задать все комбинации совместной истинности/ложности пропозициональных переменных.

3. Установить последовательность определения значений связок (порядок действий), при этом последняя связка называется главной, т.к. ее значения указывают на вид формулы.

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

Например, переводом на язык КЛВ сложного высказывания «Если Ромео любит Джульетту, а Джульетта любит Ромео, то неправда, что по крайней мере одни из них не любит другого» будет формула (А ˄ В)  ¬ ( ¬ А ˅ ¬ В). Таблица истинности для этой формулы выглядит следующем образом:

А	В	¬А	¬В	А ˄ В	¬ А ˅ ¬ В	¬(¬А˅ ¬В)	(А˄ В)  ¬ ( ¬ А ˅ ¬ В)
1	1	0	0	1	0	1	1
1	0	0	1	0	1	0	1
0	1	1	0	0	1	0	1
0	0	1	1	0	1	0	1

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

Построение полных таблиц истинности бывает весьма трудоемким процессом, поскольку число строк в таблице увеличивается по указанной выше формуле с увеличением числа пропозициональных переменных: так, при трех переменных строк будет 8, при четырех – 16, при пяти – 32. Поэтому возможно использовать два пути: путь «сжатия» записи полной таблицы или использование метода сокращенных таблиц. Рассмотрим их.

Пусть нам дана формула ((АВ) ˄ (¬В˅С))  (АС). Ясно, что число строк в ней будет 8. Будем заполнять таблицу значениями истинности как переменных, так и полученных результатов значений истинности сложных формул (от простого к сложному), ставя их под соответствующими переменными и логическими операторами. Заметим, что значения истинности переменных в формуле и их сочетания достаточно просто: первая по перечню слева направо переменная получит в данной формуле подряд четыре значения «истинно», четыре значения «ложно», вторая переменная – два «истинно», два «ложно», вновь два «истинно» и два «ложно». Истинностные значения для третьей переменной будут чередоваться. Если, скажем, формула будет содержать четыре переменных, то схема повторится: для первой будет подряд восемь значений «истинно», восемь «ложно», для второй они будут записываться по четыре подряд, для третьей – по два, для четвертой будут просто чередоваться. Такое мнемоническое правило позволяет легко заполнить «входную» часть таблицы. Поэтапно это будет выглядеть следующим образом:

(	(	А		В	)	˄	(	¬	В	˅	С	)	)		(	А		С	)
		1
		1
		1
		1
		0
		0
		0
		0

Второй этап

(	(	А		В	)	˄	(	¬	В	˅	С	)	)		(	А		С	)
		1		1
		1		1
		1		0
		1		0
		0		1
		0		1
		0		0
		0		0

Третий этап

(	(	А		В	)	˄	(	¬	В	˅	С	)	)		(	А		С	)
		1		1							1
		1		1							0
		1		0							1
		1		0							0
		0		1							1
		0		1							0
		0		0							1
		0		0							0

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

(	(	А		В	)	˄	(	¬	В	˅	С	)	)		(	А		С	)
		1		1				0			1					1		1
		1		1				0			0					1		0
		1		0				1			1					1		1
		1		0				1			0					1		0
		0		1				0			1					0		1
		0		1				0			0					0		0
		0		0				1			1					0		1
		0		0				1			0					0		0

Следующим шагом определим значение истинности выражения ((АВ) в соответствии с действием оператора импликации. Таблица примет следующий вид:

(	(	А		В	)	˄	(	¬	В	˅	С	)	)		(	А		С	)
		1	1	1				0			1					1		1
		1	1	1				0			0					1		0
		1	0	0				1			1					1		1
		1	0	0				1			0					1		0
		0	1	1				0			1					0		1
		0	1	1				0			0					0		0
		0	1	0				1			1					0		1
		0	1	0				1			0					0		0

Проделаем ту же операцию для выражения (¬В˅С). Таблица примет вид:

(	(	А		В	)	˄	(	¬	В	˅	С	)	)		(	А		С	)
		1	1	1				0		1	1					1		1
		1	1	1				0		0	0					1		0
		1	0	0				1		1	1					1		1
		1	0	0				1		1	0					1		0
		0	1	1				0		1	1					0		1
		0	1	1				0		0	0					0		0
		0	1	0				1		1	1					0		1
		0	1	0				1		1	0					0		0

Теперь определим значение истинности посылок, то есть в данной формуле, которая представляет собой импликацию, значение истинности ее антецедента, ((АВ) ˄ (¬В˅С)). Таблица будет выглядеть как

(	(	А		В	)	˄	(	¬	В	˅	С	)	)		(	А		С	)
		1	1	1		1		0		1	1					1		1
		1	1	1		0		0		0	0					1		0
		1	0	0		0		1		1	1					1		1
		1	0	0		0		1		1	0					1		0
		0	1	1		1		0		1	1					0		1
		0	1	1		0		0		0	0					0		0
		0	1	0		1		1		1	1					0		1
		0	1	0		1		1		1	0					0		0

Определим значение истинности выражения (АВ):

(	(	А		В	)	˄	(	¬	В	˅	С	)	)		(	А		С	)
		1	1	1		1		0		1	1					1	1	1
		1	1	1		0		0		0	0					1	0	0
		1	0	0		0		1		1	1					1	1	1
		1	0	0		0		1		1	0					1	0	0
		0	1	1		1		0		1	1					0	1	1
		0	1	1		0		0		0	0					0	1	0
		0	1	0		1		1		1	1					0	1	1
		0	1	0		1		1		1	0					0	1	0

Теперь, сравнивая значения истинности всего антецедента и консеквента, получим итоговое

(	(	А		В	)	˄	(	¬	В	˅	С	)	)		(	А		С	)
		1	1	1		1		0		1	1			1		1	1	1
		1	1	1		0		0		0	0			1		1	0	0
		1	0	0		0		1		1	1			1		1	1	1
		1	0	0		0		1		1	0			1		1	0	0
		0	1	1		1		0		1	1			1		0	1	1
		0	1	1		0		0		0	0			1		0	1	0
		0	1	0		1		1		1	1			1		0	1	1
		0	1	0		1		1		1	0			1		0	1	0

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

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

Продемонстрируем на примере той же самой формулы метод сокращенных таблиц. По сути он представляет собой прием рассуждения от противного. Правда, если с помощью построения полных таблиц истинности можно определить, какой именно – тождественно-истинной, тождественно-ложной ли случайно истинной – является данная формула, то сокращенные таблицы позволяют ответить на вопрос только о том, является или нет формула тождественно-истинной. Впрочем, как увидим далее, для использования логики высказываний в определении корректности некоторых рассуждений именно и требуется. Итак, предположим, что формула ((АВ) ˄ (¬В˅С))  (АС) не является тождественно-истинной, то есть в итоговом столбце встречается хоть одно значение «ложно». Поскольку формула представляет собой импликацию, это значит, что ((АВ) ˄ (¬В˅С)) истинна, а (АС) – ложна. Ложность последней возможна только тогда, когда А истинно, а С ложно. Истинность же конъюнкции ((АВ) ˄ (¬В˅С)) означает, что истинны как ((АВ), так и (¬В˅С). В первую из упомянутых формул подставим истинно значение А, тогда В может принимать значение только «истинно». Во второй формуле (¬В˅С) С ложно, а сама формула истинна. Дизъюнкция истинна, если истинен по меньшей мере один дизъюнкт; ясно, что истинно (¬В), тогда В ложно. Получаем противоречие: В одновременно приобретаем взаимоисключающие значения «истинно» и «ложно», что невозможно по определению. Наличие данного противоречия означает, что наше исходное предположение ложно, и данная формула является тождественно-истинной. (Противоречие может быть обнаружено и в каком-либо ином варианте – важно то, что если оно есть, оно непременно будет обнаружено.) Все наше рассуждение может быть записано следующим образом (каждая нижеследующая строка означает шаг рассуждения, хотя на самом деле мы разбираем всего одну строку таблицы):

(	(	А		В	)	˄	(	¬	В	˅	С	)	)		(	А		С	)
														0
						1											0
																1		0
			1							1
	1
				1
								1			0
									0

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

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

Рассмотрим решение следующей учебной задачи: Определите корректность рассуждения средствами логики высказываний «Если человек говорит неправду, то он заблуждается или сознательно вводит в заблуждение других. Этот человек говорит неправду, но явно не заблуждается. Следовательно, он сознательно вводит в заблуждение других.»

Определим с помощью квадратных скобок пропозициональные переменные, подчеркнем выражения, соответствующие логическим операторам. Получим: «Если[ человек говорит неправду], то [он заблуждается] или [сознательно вводит в заблуждение других]. [Этот человек говорит неправду], но [явно не заблуждается]. Следовательно,[он сознательно вводит в заблуждение других].» Пусть А есть «человек говорит неправду», В – «он заблуждается», С – «сознательно вводит в заблуждение других». При переводе рассуждения в логическую нотацию, посылки рассуждения обычно связываются с помощью оператора конъюнкции, между совокупностью посылок и заключением обычно ставится импликация, по смыслу наиболее точно отражающая переход от посылок к заключению рассуждения. В результате получим формулу следующего вида, отражающую структуру (форму) данного рассуждения: ((А (В˅С)) ˄ (А˄

¬В))  С. Построим сокращенную таблицу истинности для данной формулы.

(	(	А		(	В	˅	С	)	)	˄	(	А	˄	¬	В	)	)		С
																		0
										1									0
			1										1
												1		1
															0
		1				1
							0
					1

Видим противоречие (указано стрелкой). Следовательно, наше предположение было неверно, данная формула является тождественно-истинной (общезначимой). Заключение С логически следует из посылок ((А (В˅С)) ˄ (А˄ ¬В)). Отсюда заключаем, что рассуждение, структура которого была проанализирована средствами логики высказываний, является корректным, q.e.d.

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

Правила редукции.

:

А  В

():

(А  В)

:

А  В

():

(А  В)

():

А

А, В

А | В

А | В

А, В

А

:	А В			():	(А В)
	А | В				А, В

Формула, расположенная над чертой правила, называется посылкой правила редукции, а формула под чертой правила – называется заключением правила. Вертикальная черта в заключении правила означает ветвление результата применения правила редукции (правила с ветвлением).

Определение 1 (аналитической таблицы). Аналитической таблицей называется конечная или бесконечная последовательность строк С₁, …С_к, …списков формул такая, что каждая последующая строка получается из предыдущей применением правила редукции.

Замечание. Отметим, что если мы применяем правило редукции с ветвлением, то мы получаем два списка формул.

Определение 2 (замкнутого списка формул). Список формул называется замкнутым, если в списке встречается некоторая формула и ее отрицание, т.е. А и А (противоречие).

Определение 3 (завершенного списка). Список формул называется завершенным, если к формулам этого списка невозможно применять правила редукции, т.е в списке встречаются атомарные формулы или отрицание атомарных формул.

Определение 4 (замкнутой таблицы). Аналитическая таблица замкнута, если все ее списки формул замкнуты (противоречивы).

Определение 5 (завершенной таблицы). Аналитическая таблица называется завершенной, если она замкнута или имеет завершенные списки формул.

Определение 6 (общезначимой формулы в терминах аналитической таблицы). Формула А называется общезначимой, если ее аналитическая таблица замкнута.

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

Натуральное исчисление высказываний.

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

Замечание. В натуральном исчислении преобразования формул строятся только на основе правил. Алфавит языка этого исчисления и определение правильно построенной формулы совпадает с алфавитом и понятием формулы логики высказываний, заданных выше. А понятиям логического закона и логического следования здесь вводятся синтаксические аналоги – понятие теоремы и понятие выводимости.

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

- задать правила вывода;

- сформулировать понятия вывода и выводимой формулы.

Правила вывода.

Правила вывода делятся на правила введения логических связок и удаление логических связок и. В формулировке правил «В:» сокращает слово «Введение», а «У:» - «Удаление».

В: 	А	В: 	В		У: 	Г, А  В;	Г, А├ С	Г, В├ С
	А  В		А  В				Г├ С
В: 		А, В		У: 		А В	У: 	А  В
		А  В				А		В

В: 	Г, А ├В	У: 	А, А  В
	Г ├ А  В		В

У:	 А		В: 	Г, А ├ В; Г, А ├ В
	А			Г├ В

У(слабое): 	А, А
	В

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

Определение 2. (выводимой формулы). Последняя формула в выводе называется выводимой формулой.

Комментарии к правилам вывода. Над чертой правила - посылки, под чертой правила – заключение. Правила делятся на однопосылочные (над чертой пишется одна формула) и двухпосылочные (над чертой пишутся две формулы). Правила делятся на правила прямого вывода и правила косвенного вывода. В правилах косвенного вывода в посылках используется знак выводимости «├», который означает, что строятся вспомогательные выводы. Правило В:  предполагает доказательство теоремы дедукции.