3. Основные направления и понятия символической (математической) логики	35

3.4. Семантика языка логики высказываний

Правила интерпретации высказываний

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

Интерпретация проходит по следующим правилам.

1.Пропозициональные переменные произвольным образом принимают зна- чения Л или И.

2.Если А имеет значение Л, то А принимает значение И, а если А имеет значение И, то А принимает значение Л. Другими словами, если А — ложно, то

А — истинно, а если А — истинно, то А — ложно.

Изложенное можно выразить в виде истинностной таблицы.

ÀÀ

		Истинностная таблица для отрицания
È	Ë

ËÈ

3.Конъюнкция двух высказываний истинна в том и только в том случае, если истинны оба высказывания.

À	Â	(À & Â)
È	È	È
			Истинностная таблица для конъюнкции
È	Ë	Ë
Ë	È	Ë
Ë	Ë	Ë

4. Дизъюнкция ложна в том и только в том случае, если ложно каждое из двух высказываний.

À	Â	(À Â)
È	È	È
È	Ë	È	Истинностная таблица для дизъюнкции
Ë	È	È
Ë	Ë	Ë

5.Импликация ложна в том и только в том случае, если ее антецедент истинен,

àконсеквент ложен. Если (А В), то А называют антецедентом, а В — консеквентом.

À	Â	(À Â)
È	È	È
			Истинностная таблица для импликации
È	Ë	Ë
Ë	È	È
Ë	Ë	È

36I. Пропедевтика: предмет логики. Основные понятия и структура логики

3.5.Семантические таблицы логики высказываний

Семантические таблицы устанавливают отношения истинности разных высказываний.

Когда с помощью логических связок простые высказывания (не содержащие логических связок) образуют сложное высказывание, встает вопрос: при каких условиях сложное высказывание можно считать истинным, а при каких — ложным?1 Ответ на этот вопрос дают таблицы истинности.

Таблица истинности устанавливает истинностное значение сложного высказывания при различных наборах значений входящих в него простых высказываний.

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

Значение истинности (или истинностное значение) сокращенно обозначают русскими буквами: И — для истинно и Л — для ложно.

				Таблицы истинности
для отрицания					для конъюнкции, дизъюнкции, импликации
A			A		A		Â	À & Â		À Â	À Â
					È		È	È		È	È
È		Ë
Ë		È			È		Ë	Ë		È	Ë
					Ë		È	Ë		È	È
					Ë		Ë	Ë		Ë	È

1 Эта задача носит название проблемы разрешимости. Для формул языка логики высказываний в качестве разрешающей процедуры можно использовать построение таблицы истинности для данной формулы (см. п. 3.6—3.8), приведение формулы к конъюнктивной (КНФ) или дизъюнктивной (ДНФ) нормальной форме (см. п. 3.10—3.12) и логические исчисления как метод решения проблемы разрешимости. Наиболее известными являются исчисления следующих видов:

аксиоматические, системы натурального вывода и секвенциальные исчисления (см. п. 3.13—3.16).

3. Основные направления и понятия символической (математической) логики	37

3.6. Семантическая проблема разрешимости

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

Такой общий метод или способ является процедурой (алгоритмом) и называется разрешающей процедурой1, а теория, в рамках которой такая процедура действует, разрешимой теорией.

Логика высказываний является разрешимой теорией. В логике высказываний сложные суждения переводятся с естественного языка на символический язык с использованием символов и правил построения формул из этих символов. Формулы являются результатом этого перевода. Различают три вида формул2:

1)тождественно истинные, если формула принимает значение «истина» при всех наборах значений пропозициональных переменных, входящих в ее состав;

2)тождественно ложные, если формула принимает значение «ложь» при всех наборах значений пропозициональных переменных, входящих в ее состав;

3)собственно выполнимые (нейтральные), если формула принимает значения

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

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

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

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

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

1. Табличный способ определения типа формул.

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

2. Способ приведения формулы к нормальной форме.

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

3. Аксиоматические исчисления.

Этот вид исчисления включает в себя аксиомы и правила вывода. 4. Натуральные исчисления.

Этот вид исчисления более адекватно моделирует процесс рассуждения и не содержит аксиом.

5. Секвенциальные исчисления.

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

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

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

38I. Пропедевтика: предмет логики. Основные понятия и структура логики

3.7.Табличный способ определения типа формул

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

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

Приведем выражение:

«Если мы вовремя сдадим экзамены (р) и успешно закончим семестр (q), то на каникулы поедем в горы (r)».

Формула: (р & q) r.

Построим таблицу истинности для данной формулы. Число строк таблицы истинности в общем случае определяется по следующей формуле: х = 2n, где n — число различных переменных, входящих в формулу, а цифра 2 показывает число истинности значений (И, Л): две переменных — 4 строки; три — 8 строк; четыре переменные — 16 строк, пять – 32 строки и т.д.

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

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

Выполнимая формула та, которая мо-

	p	q	r	(p	&	q)		r
	È	È	È	È	È	È È		È
	È	È	Ë	È	È	È Ë		Ë
	È	Ë	È	È	Ë	Ë	È	È
	È	Ë	Ë	È	Ë	Ë	È	Ë
	Ë	È	È	Ë	Ë	È È		È
	Ë	È	Ë	Ë	Ë	È	È	Ë
	Ë	Ë	È	Ë	Ë	Ë	È	È
	Ë	Ë	Ë	Ë	Ë	Ë	È	Ë
Порядок решения:					1		2

жет принимать, по крайней мере, одно значение «истина». Тождественно-истин- ной формулой (или тавтологией, или законом логики) называется формула, ко-

торая при любых комбинациях значений

входящих в нее переменных принимает значение «истина». Формула, принимающая при всех распределениях значение «ложно», называется противоречием.

Результирующий столбец таблицы выделен жирным шрифтом.