Краткое введение в логику высказываний

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

Обо всем этом написано много умных книжек разными авторами в разное время на разных языках... Можно найти много "поучительных" ссылок в интернете... Я не стремлюсь объять необъятное (хотя иногда очень хочется), моя цель - постараться преподнести материал как инструмент для решения ряда интересных задач обычно бывает наоборот:) - задачи служат для понимания, осмысления и запоминания пройденного).

Это краткое введение, разумеется, не исчерпывает тему полностью, и если у вас возникают вопросы, спрашивайте.

Для начала несколько определений от mega.km.ru (можно пропустить:)):

ЛОГИКА ВЫСКАЗЫВАНИЙ, раздел логики, в котором вопрос об истинности или ложности высказываний рассматривается и решается на основе изучения способа построения высказываний из т.н. элементарных (далее не разлагаемых и не анализируемых) высказываний с помощью логических операций конъюнкции ("и"), дизъюнкции ("или"), отрицания ("не"), импликации ("если..., то...") и др. Логику высказываний, задаваемую системой постулатов (аксиом и правил вывода), называют исчислением высказываний.

ВЫСКАЗЫВАНИЕ, мысль, выраженная повествовательным предложением и могущая быть истинной или ложной.

АНАЛИТИЧЕСКОЕ ВЫСКАЗЫВАНИЕ, высказывание, истинность или ложность которого может быть установлена исключительно на основе анализа его грамматической или логической структуры. Примеры истинных аналитических высказываний логические законы.

СУЖДЕНИЕ, форма мышления, представляющая собой сочетание понятий, из которых одно (субъект) определяется и раскрывается через другое (предикат).

ЛОГИЧЕСКИЙ ЗАКОН, название законов, образующих основу логической дедукции; схема логической связи высказываний, выражаемая общезначимой формулой логики (аксиомой или теоремой), убедительность которой вытекает из одного только истолкования входящих в нее логических операций и по существу не связана с фактической истинностью "наполняющих" ее высказываний.

ТОЖДЕСТВЕННАЯ ИСТИННОСТЬ, свойство сложных высказываний быть истинными в силу своей формально-логической структуры и смысла используемых в них логических операций. Будучи независимыми от содержания входящих в них конкретных высказываний, тождественно-истинные высказывания выступают в качестве логических законов.

Итак, какие бывают высказывания?

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

А можно взять для примера более определенное (в смысле значения истинности) высказывание "Луна - спутник Земли" - простое и истинное. А вот "Солнце - спутник Земли" будет ложным высказывание (и простым). Усложняем задачу: "Луна - спутник Земли и Солнце - спутник Земли". На этот раз наше высказывание сложное, т.к. оно состоит из двух простых, и, что самое важное, это высказывание ложное, так уж устроена логическая (пропозициональная) связка "и" (конъюнкция). Если она обьединяет истинные высказывания - сложное высказывание будет истинным, а во всех остальных случаях - ложным. А сколько всего случаев? Каждое высказывание может быть истинным или ложным, если рассматривать два высказывания, то получим 4 комбинации: оба истинные, оба ложные, одно истинное, другое ложное, и наоборот.

Рассмотрим теперь высказывание "Луна - спутник Земли или Солнце - спутник Земли" - сложное и истинное. На этот раз связующим звеном выступает "или" (дизъюнкция), которая принимает ложное значение только когда все входящие высказывания - ложные, если хотя бы одно истинное, то все дизъюнктивное высказывание - истинное.

Но мы еще можем превратить высказывание "Луна - спутник Земли" в ложное, а "Солнце - спутник Земли" в истинное, если скажем "Неверно, что Луна - спутник Земли" и "Неверно, что Солнце - спутник Земли". Так действует на высказывания связка "не" (отрицание): истинные высказывания превращает в ложные, а ложные - в истинные. Теперь высказывание "Луна - спутник Земли и неверно, что Солнце - спутник Земли" - истинное, "Неверно, что Луна - спутник Земли или Солнце - спутник Земли" - ложное.

Еще одна интересная связка "если..., то..." (импликация). Рассмотрим высказывание "Если Луна - спутник Земли, то и Солнце - спутник Земли". Здравый смысл подсказывает, что это высказывание ложное, но истинным будет "Если Луна - спутник Земли, то неверно, что Солнце - спутник Земли". Высказывание же "Если Солнце - спутник Земли, то и Луна - спутник Земли" - истинное, несмотря на кажущуюся абсурдность. И высказывание "Если Солнце - спутник Земли, то все что угодно" - тоже истинное. В таких случаях мне нравится высказывaние "Если я - балерина, то Луна - зеленая" или что-нибудь подобное.

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

a	b

Два высказывания - 4 строчки в таблице. Три различных высказывания - 8 комбинаций, 4 - 16 и т.д. n высказываний - 2n комбинаций.

a	b	c

Какие символы лучше использовать для обозначения логических связок? Фантазия в этой области безгранична...:) Трудно найти две книги, в которых авторы придерживались бы одинаковых обозначений. Тем не менее, некоторая логика:) в этом есть. Но далеко не все символы могут быть воспроизведены в электронном тексте, поэтому часто прибегают к включению в текст небольших графических файлов...
Остановимся пока на следующих обозначениях:

отрицание "неверно что...", "не..." ~a. конъюнкция "... и..." a & b (a, b - конъюнкты). дизъюнкция "... или..." a v b (a, b - дизъюнкты). импликация "если..., то..." a => b (a - основание, b - следствие). эквивалентность (равнозначность) "... тогда и только тогда...", "... если и только если..." a <=> b.

Обычно логические значения результатов применения связок записываются в виде таблиц (т.н. таблицы истинности). Но представление этих таблиц широко варьируется. Для обозначения высказываний, логических значений и связок используют как прописные, так и строчные буквы. Для обозначения истинности и ложности используют, соответственно, "1" и "0", "И" и "Л", "t" (true) и "f"(false)... Кому-то удобнее сначала выписывать "0", а потом "1", а кому-то - наоборот. Ниже представлены различные способы изображения таблицы истинности на примере дизъюнкции. Я предпочитаю первый вариант.

a V b

a b a V b

A V B

a b a или b и и и и л и л и и л л л

p OR q F F F F T T T T F T T T

Таблицы для связок:

a ~a

a & b

a V b

a => b

a <=> b

Последовательность выполнения операций в сложных высказываниях: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность.

Дизъюнкцию "или" часто называют "нестрогой дизъюнкцией". А строгую диъюнкцию "либо..., либо..." обозначают символом "v" с точкой сверху или двойным "v" (перевернутое на 90 градусов против часовой стрелки "<<"), вероятно существуют и другие обозначения. Отличие таблицы истинности для строгой дизъюнкции от таблицы истинности для нестрогой дизъюнкции в первой строчке: когда значения а и b истинны, "либо а, либо b" - ложно.

И несколько полезных формул:

~~a == a - закон снятия двойного отрицания

a & a == a - закон идемпотентности

a v a == a - закон идемпотентности

a & 0 == 0

a & 1 == a

a v 0 == a

a v 1 == 1

a & ~a == 0 - закон противоречия

a v ~a == 1 - закон исключенного третьего

~(a & b) == ~a v ~b - закон Де Моргана

~(a v b) == ~a & ~b - закон Де Моргана

a & b == ~(~a v ~b) - закон Де Моргана

a v b == ~(~a & ~b) - закон Де Моргана

a => b == ~a v b - выражение импликации через отрицание и дизъюнкцию

a <=> b == (a => b) & (b => a)

a & (b v a) == a - закон поглощения

a v (b & a) == a - закон поглощения

a & (~a v b) == a & b

a v (~a & b) == a v b

(a & b) v (a & ~b) == a - закон склеивания

(a v b) & (a v ~b) == a - закон склеивания

a & b == b & a - коммутативность конъюнкции

a v b == b v a - коммутативность дизъюнкции

a & (b & c) == (a & b) & c - ассоциативность конъюнкции

a v (b v c) == (a v b) v c - ассоциативность дизъюнкции

a & (b v c) == (a & b) v (a & c) - дистрибутивность конъюнкции относительно дизъюнкции

a v (b & c) == (a v b) & (a v c) - дистрибутивность дизъюнкции относительно конъюнкции