Верещагин Н.К., Шень А. - Языки и исчисления, страница 2

Например,«216 + 1 — простое число» — истинное высказывание, а «232 + 1 —простое число» — ложное (это число делится на 641). Про высказывание «существует бесконечно много простых p, для которых p + 2 —также простое» никто не берётся сказать наверняка, истинно оноили ложно. Заметим, что «x делится на 2» в этом смысле не является высказыванием, пока не сказано, чему равно x; при разных xполучаются разные высказывания, одни истинные (при чётном x),другие — ложные (при нечётном x).Высказывания можно соединять друг с другом с помощью «логических связок».

Эти связки имеют довольно странные, но традиционные названия и обозначения (табл. 1.1). Отметим также, что вимпликации A ⇒ B высказывание A называют посылкой, или антецедентом импликации, а B — заключением, или консеквентом.Говорят также, что высказывание имеет истинностное значениеИ (истина), если оно истинно, или Л (ложь), если оно ложно. Иногдавместо И употребляется буква T (true) или число 1, а вместо Л —буква F (false) или число 0. (С первого взгляда идея произвольнымобразом выбрать числа 0 и 1 кажется дикой — какая бы польза моглабыть от, скажем, сложения истинностных значений? Удивительнымобразом в последние годы обнаружилось, что такая польза есть, и если оперировать с истиной и ложью как элементами конечного поля,можно получить много неожиданных результатов.

Но это выходит[п. 1]Высказывания и операциисвязкаAиBA или Bне AA неверноиз A следует Bесли A, то BA влечёт BB — следствие AобозначениеA&B A ∧ BA and BA ∨ B A or B¬A ∼ A Anot AA→B A⇒BA⊃Bif A then B9названиеконъюнкциядизъюнкцияотрицаниеимпликацияследованиеТаблица 1.1. Логические связки, обозначения и названия.за рамки нашей книги.)Логические связки позволяют составлять сложные высказыванияиз простых.

При этом истинность составного высказывания определяется истинностью его частей в соответствии с таблицей 1.2.AЛЛИИBЛИЛИA∧BЛЛЛИA∨BЛИИИA→BИИЛИAЛИ¬AИЛТаблица 1.2. Таблицы истинности для логических связок.Те же правила можно изложить словесно. Высказывание A ∧ Bистинно, если оба высказывания A и B истинны. Высказывание A∨Bистинно, если хотя бы одно из высказываний A и B истинно. Высказывание A → B ложно в единственном случае: если A истинно, аB ложно. Наконец, ¬A истинно в том и только том случае, когдаA ложно.Из всех связок больше всего вопросов вызывает импликация. Всамом деле, не очень понятно, почему надо считать, скажем, высказывания «если 2 × 2 = 5, то 2 × 2 = 4» и «если 2 × 2 = 5, то 3 × 3 = 1»истинными.

(Именно так говорят наши таблицы: Л → И = Л → Л == И.) На самом деле в таком определении есть свой резон. Все со-10Логика высказываний[гл. 1]гласны, что если число x делится на 4, то оно делится на 2. Этоозначает, что высказывание(x делится на 4) → (x делится на 2)истинно при всех x. Подставим сюда x = 5: обе части ложны, а утверждение в целом истинно.

При x = 6 посылка импликации ложна, азаключение истинно, и вся импликация истинна. Наконец, при x = 8посылка и заключение истинны и импликация в целом истинна. Сдругой стороны, обратное утверждение (если x делится на 2, то xделится на 4) неверно, и число 2 является контрпримером. При этомпосылка импликации истинна, заключение ложно, и сама импликация ложна. Таким образом, если считать, что истинность импликации определяется истинностью её частей (а не наличием между ними каких-то причинно-следственных связей), то все строки таблицыистинности обоснованы. Чтобы подчеркнуть такое узко-формальноепонимание импликации, философски настроенные логики называютеё «материальной импликацией».Теперь от неформальных разговоров перейдём к определениям.Элементарные высказывания (из которых составляются более сложные) мы будем обозначать маленькими латинскими буквами и называть пропозициональными переменными.

Из них строятся пропозициональные формулы по таким правилам:• Всякая пропозициональная переменная есть формула.• Если A — пропозициональная формула, то ¬A — пропозициональная формула.• Если A и B — пропозициональные формулы, то (A∧B), (A∨B)и (A → B) — пропозициональные формулы.Можно ещё сказать так: формулы образуют минимальное множество, обладающее указанными свойствами (слово «минимальное»здесь существенно: ведь если бы мы объявили любую последовательность переменных, скобок и связок формулой, то эти три свойствабыли бы тоже выполнены).Пусть формула ϕ содержит n пропозициональных переменныхp1 , p2 , . .

. , pn . Если подставить вместо этих переменных истинностные значения (И или Л), то по таблицам можно вычислить истинностное значение формулы в целом. Таким образом, формула задаёт некоторую функцию от n аргументов, каждый из которых может[п. 1]Высказывания и операции11принимать значения Л и И. Значения функции также лежат в множестве {Л, И}, которое мы будем обозначать B.

Мы будем следоватьуже упоминавшейся традиции и отождествлять И с единицей, а Л —с нулём, тем самым B есть {0, 1}. Формула ϕ задаёт отображениетипа Bn → B. Такие отображения называют также булевыми функциями n аргументов.Пример. Рассмотрим формулу (p ∧ (q ∧ ¬r)). Она истинна в единственном случае — когда p и q истинны, а r ложно (см.

таблицу 1.3).p00001111q00110011r ¬r0 11 00 11 00 11 00 11 0(q ∧ ¬r) (p ∧ (q ∧ ¬r))0000100000001100Таблица 1.3. Таблица истинности для (p ∧ (q ∧ ¬r)).Некоторые формулы выражают логические законы — составныевысказывания, истинные независимо от смысла их частей.

Такиеформулы (истинные при всех значениях входящих в них переменных) называют тавтологиями.Пример. Формула ((p ∧ q) → p) является тавтологией (это можнопроверить, например, составив таблицу). Она выражает такой логический закон: из конъюнкции утверждений следует первое из них.1. Как выглядит симметричное утверждение для дизъюнкции и какаяформула его выражает?Две формулы называют эквивалентными, если они истинны приодних и тех же значениях переменных (другими словами, если онизадают одну и ту же булеву функцию). Например, легко проверить,что формула (p ∧ (p → q)) истинна лишь при p = q = И, и потомуэквивалентна формуле (p ∧ q).Рассмотрим формулу ((p ∧ q) ∨ q).

Она истинна, если переменная q истинна, и ложна, если переменная q ложна. Хотелось бысказать, что она эквивалентна формуле q, но тут есть формальнаятрудность: она содержит две переменные и потому задаёт функциюот двух аргументов (типа B × B → B), в то время как формула q12Логика высказываний[гл. 1]задаёт функцию одного аргумента.

Мы не будем обращать на этовнимания и будем считать эти формулы эквивалентными. Вообще,если есть список переменных p1 , . . . , pn , содержащий все переменные некоторой формулы ϕ (и, возможно, ещё какие-то переменные),можно считать, что формула ϕ задаёт функцию от n аргументов,возможно, на деле зависящую не от всех аргументов (постоянную понекоторым аргументам)После сделанных оговорок легко проверить следующий факт:формулы ϕ и ψ эквивалентны тогда и только тогда, когда формула((ϕ → ψ) ∧ (ψ → ϕ)) является тавтологией. Используя сокращение(p ↔ q) для ((p → q) ∧ (q → p)), можно записывать утвержденияоб эквивалентности формул в виде тавтологий.

Вот несколько такихэквивалентностей:Теорема 1. Формулы(p ∧ q) ↔ (q ∧ p);((p ∧ q) ∧ r) ↔ (p ∧ (q ∧ r));(p ∨ q) ↔ (q ∨ p);((p ∨ q) ∨ r) ↔ (p ∨ (q ∨ r));(p ∧ (q ∨ r)) ↔ ((p ∧ q) ∨ (p ∧ r));(p ∨ (q ∧ r)) ↔ ((p ∨ q) ∧ (p ∨ r));¬(p ∧ q) ↔ (¬p ∨ ¬q);¬(p ∨ q) ↔ (¬p ∧ ¬q);(p ∨ (p ∧ q)) ↔ p;(p ∧ (p ∨ q)) ↔ p;(p → q) ↔ (¬q → ¬p);p ↔ ¬¬pявляются тавтологиями. Первые четыре эквивалентности выражают коммутативностьи ассоциативность конъюнкции и дизъюнкции. Проверим, например,вторую: левая и правая части истинны в единственном случае (когдавсе переменные истинны), и потому эквивалентны.

(Для дизъюнкции удобнее смотреть, когда она ложна.)Две следующие эквивалентности означают дистрибутивность —заметим, что в отличие от сложения и умножения в кольцах здесьверны оба свойства дистрибутивности. Проверить эквивалентностьлегко, если отдельно рассмотреть случаи истинного и ложного p.[п. 1]Высказывания и операции13Следующие два свойства, законы Де Моргана, легко проверить,зная, что конъюнкция истинна, а дизъюнкция ложна лишь в одном случае.

Эти свойства иногда выражают словами: «конъюнкциядвойственна дизъюнкции».Далее следуют два очевидных закона поглощения (один из нихмы уже упоминали).За ними идёт правило контрапозиции, которое говорит, в частности, что утверждения «если x совершенно, то x чётно» и «если xнечётно, то x несовершенно» равносильны. Хотя оно и очевидно проверяется с помощью таблиц истинности, с ним связаны любопытныепарадоксы. Вот один из них.Биолог А выдвинул гипотезу: все вороны чёрные.

Проверяя её,он вышел во двор и обнаружил на дереве ворону. Она оказалосьчёрной. Биолог А радуется — гипотеза подтверждается. Биолог Бпереформулировал гипотезу так: все не-чёрные предметы — не вороны (применив наше правило контрапозиции) и не стал выходитьво двор, а открыл холодильник и нашёл там оранжевый предмет. Оноказался апельсином, а не вороной. Биолог Б обрадовался — гипотеза подтверждается — и позвонил биологу А.