15

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

Математические символы – те письмена, которыми Бог начертил великую книгу Природы. Не знающий их не в состоянии понять в ней ни одного слова и обречен вечно блуждать по лабиринту в кромешной тьме….

Г. Галилей

§ 2. Пропозициональные буквы, связки и формы (формулы логики высказываний). Построение таблиц истинности

Символы , &, , ,≡ называются пропозициональными связками.

Заглавные буквы алфавита (А,В,С,...) и те же буквы с числовыми индексами (А1,А2,...,В1,В2,...,С1,С2,...) называются пропозициональными буквами. Считается, что каждая пропозициональная буква может принимать значение И либо Л.

Выражением называется конечная последовательность определенных символов. Например, А& В - выражение, построенное из символов , &, А и В, а ?§!! - выражение, построенное из символов ?, § и !.

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

Индуктивное определение пропозициональной формы:

1)все пропозициональные буквы суть пропозициональные формы,

2)если А и В пропозициональные формы, то ( А), (А&В), (А В), (А B), (А≡B) тоже пропозициональные формы,

3)только те выражения являются пропозициональными формами, для которых это следует из пп.1,2.

Примеры пропозициональных форм: A, ( В),	((А&В) ( C)),
((( А) В)≡С).

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

Жирные заглавные буквы латинского алфавита (А,В,C ,...) или те же буквы с числовыми индексами (А1,А2,...,В1,В2,...,С1,С2,...) употребляются для обозначения произвольных пропозициональных форм, тогда как обычное написание этих букв применяется лишь для пропозициональных букв.

16

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

Составное (сложное) высказывание, образованное с помощью введенных операций , &, , , ≡ будет истинным либо ложным в зависимости от значений исходных высказываний. Следовательно, полученное составное высказывание порождает некоторую истинностную функцию.

Как определено выше, каждая пропозициональная буква может принимать значения И либо Л. Будем считать, что пропозициональные формы ( А), (А&В), (А В), (А В) и (А ≡Β) имеют те же таблицы истинности, что и обозначаемые таким образом высказывания (см.§1). Тогда каждому распределению (истинностных) значений И и Л пропозициональных букв, входящих в пропозициональную форму, соответствуют согласно таблицам истинности для пропозициональных связок некоторые истинностные значения этой пропозициональной формы.

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

Заметим, что пропозициональная форма не является высказыванием. По определению пропозициональная форма - это выражение, построенное из пропозициональных букв, т.е. букв А, В, С,..., А1 ,А2 ,..., В1 ,В2 ,..., С1,С2,... с помощью пропозициональных связок согласно правилам 1), 2), 3) и ничего более. В частном случае пропозициональные буквы могут обозначать высказывания, пропозициональные связки - логические операции, тогда пропозициональная форма будет обозначать некоторое высказывание. Истинностное значение полученного высказывания можно определить с помощью таблиц истинности.

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

букв, имеет таблицу истинности					с 2n строками.		Например, для формы
(((А&В) С) А) имеем следующую таблицу истинности.
А	B	C	(A&B)		((А&В) С)		(((А&В) С) А)
Л	Л	Л	Л		Л		И
Л	Л	И	Л		И		Л
Л	И	Л	Л		Л		И
Л	И	И	Л		И		Л
И	Л	Л	Л		Л		И
И	Л	И	Л		И		И
И	И	Л	И		И		И
И	И	И	И		И		И

17

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

	A	B	C		((( А & В) С) А)
	Л	Л	Л		Л	Л	И
	Л	Л	И		Л	И	Л
	Л	И	Л		Л	Л	И
	Л	И	И		Л	И	Л
	И	Л	Л		Л	Л	И
	И	Л	И		Л	И	И
	И	И	Л		И	И	И
	И	И	И		И	И	И
	Следующий метод построения таблиц истинности, называют
алгоритмом Квайна. В форме					выбирается некоторая буква, например, та

буква, которая чаще всего встречается в рассматриваемой форме. Выбранной букве (для формы D=(((А&В) С) А) это будет буква А) приписывается значение И либо Л. Далее проводят вычисления, где возможно, при выбранном значении этой буквы. Если А=И, то для формы D=(((А&В) С) А), вне зависимости от значении букв В и С, легко получить, что D=И. При А=Л и С=Л получим снова, что D=И. Наконец, если А=Л и С=И, то D=Л. В результате получим сокращенную запись таблицы истинности содержащую всего три строки (в данном случае результат не зависит от значений буквы В, а при А=И не зависит и от значений С):

A	B	C	(((А&В) С) А)
Л		Л	И
Л		И	Л
И			И

§ 3. Упрощения в записях пропозициональных форм

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

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

Во-вторых, если форма содержит вхождения только одной бинарной связки (т.е. &, , или ≡), то для каждого вхождения этой связки опускаются внешние скобки у той из двух форм, соединяемых этим вхождением, которая стоит слева.

18

Пример. А В С А пишется вместо (((А В) С) А), а В В А (С А) пишется вместо (((В В) А) (С А)).

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

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

Пример. В форме А≡ А&В С D скобки восстанавливаются следующими шагами:

А≡( А)&В С ( D),

А≡(( А)&В) С ( D),

А≡(( А)&В) (C ( D)),

А≡((( А)&В) (С ( D))),

(А≡((( А)&В) (С ( D)))).

Однако не всякая форма может быть записана без скобок. Например, нельзя опустить оставшиеся скобки в формах: А&(В С), А (В C), (А В).

Приходится порой простые мысли доказывать всерьез, как теоремы.

О. Сулейменов1

§ 4. Тавтологии (общезначимые формулы). Противоречия

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

Таблица истинности тавтологии имеет результирующий столбец, состоящий только из И.

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

А А, (А≡В)≡ (В≡А).

Противоречием (тождественно ложной пропозициональной формой)

называется пропозициональная форма, принимающая значение Л при любой

1 Казахстанский поэт.

19

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

Примеры противоречий: А& А, (А А), (А≡ А).

Истинностная таблица для противоречия, очевидно, имеет в результирующем столбце только значения Л.

Очевидно, что пропозициональная форма А является тавтологией тогда и только тогда, когда А есть противоречие.

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

Теорема 1.1. Если А и (А В) - тавтологии, то В - тавтология.

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

Теорема 1.2. Если А есть тавтология, содержащая пропозициональные буквы А1, А2,..., Аn, и В получается из А подстановкой в А пропозициональных форм А1, А2,... Аn вместо букв А1, А2,..., Аn соответственно, то В есть тавтология, т.е. подстановка в тавтологию приводит к тавтологии.

Доказательство. Пусть задано произвольное распределение истинностных значений для пропозициональных букв, входящих в В. Формы А1 , А2 ,..., Аn примут тогда некоторые значения х1, х2,..., хn (каждое хi есть И или Л). Если мы придадим значения х1, х2,..., хn соответственно буквам А1, А2,..., Аn , то так как А есть тавтология, то А будет истинно, и это же значение принимает В. Таким образом, при произвольных значениях пропозициональных букв форма В принимает значение И, что и

требовалось доказать.

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

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

20

всегда истинно (логически истинно), в то время как высказывание: "Иванов - студент", если и истинно, то в силу уже других причин.

Высказывание, которое можно получить с помощью подстановки в противоречие, называется логически ложным высказыванием. Примером логически ложного высказывания может служить высказывание: "2х2=4 и 2х2≠4", где имеет место одновременно какое-то высказывание и отрицание этого же высказывания.

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

Например, А&В является выполнимой пропозициональной формой, так как принимает значения И, когда А=И и В=И, а форма А& А не будет выполнимой, так как всегда ложна.

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

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

Ясно, что выяснение выполнимости А равносильно выяснению, является ли А противоречием или нет, что, в свою очередь, равносильно выяснению, является ли А тавтологией или нет. Таким образом, если есть метод, позволяющий для произвольной формы конечным числом действий выяснить, тавтология это или нет, то можно решить вопрос выполнима или нет произвольная форма А. Для этого достаточно выяснить А - тавтология или нет. Если А - тавтология, то А - противоречие, следовательно, А невыполнимо, если же А - не тавтология, то А выполнимо.

Проблема разрешимости (алгебры высказываний) полностью решается, например, с помощью таблиц истинности. Если пропозициональная форма содержит n различных букв, то, как известно, ее таблица истинности имеет 2n строк. При больших значениях n составление таблиц истинности и выяснение выполнимости по ним является громоздкой операцией. Для решения проблемы разрешимости существуют и другие способы, основанные на приведении к так называемым нормальным формам. Эти формы и способы решения с их помощью проблемы разрешимости будут рассмотрены ниже.

Шел я садом однажды и вдруг увидал, Как делили коврижку Сова и Шакал. И коврижку Шакал проглотил целиком,

АСове только блюдечко дал с ободком.

Апотом предложил ей: «Закончим дележ – Ты возьми себе ложку, я – вилки и нож». И наевшись, улегся Шакал на траву,

Но сперва на десерт проглотил он…