• Логика высказываний: определение и применение
  • Логические операции над высказываниями
  • Формулы логики высказываний
  • Тавтологии и противоречия
  • Заставляем компьютер понимать «если …, то…»
  • Посылки и выводы. Валидный и не валидный аргумент
  • Применение логики высказываний в информатике и программировании

Будут и задачи для самостоятельного решения, к которым можно посмотреть ответы.

Логика высказываний: определение и применение

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

Высказываниями принято считать такие предложения (написанные на «словесном» либо математическом языке), о которых можно сказать одно из двух: либо они являются истинными, либо ложными.

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

Логика высказываний отвлекается от содержательной нагрузки высказываний и изучает их истинностное значение, то есть является ли высказывание истинным или ложным.

Рисунок слева — иллюстрация явления, известного как «Парадокс лжеца». При этом, на взгляд автора проекта, такие парадоксы возможны только в средах, несвободных от политических заморочек, где на ком-то могут априори поставить клеймо лжеца. В естественном многослойном мире на предмет «истины» или «лжи» оцениваются только отдельно взятые высказывания. И далее на этом уроке вам представится возможность самим оценить на этот предмет немало высказываний (а затем посмотреть правильные ответы). В том числе сложных высказываний, в которых более простые связаны между собой знаками логических операций. Но прежде рассмотрим сами эти операции над высказываниями.

Логические операции над высказываниями

Итак, высказывания можно рассмотривать как величину, которая может принимать два значения: «истина» и «ложь».

Например, даны суждения: «собака — животное», «Париж — столица Италии», «3

Первое из этих высказываний может быть оценено символом «истина», второе — «ложь», третье — «истина» и четвёртое — «ложь». Такая трактовка высказываний составляет предмет алгебры высказываний. Будем обозначать высказывания большими латинскими буквами A, B, …, а их значения, то есть истину и ложь, соответственно И и Л. В обычной речи употребляются связи между высказываниями «и», «или» и другие.

Эти связи позволяют, соединяя между собой различные высказывания, образовывать новые высказывания — сложные высказывания. Например, связка «и». Пусть даны высказывания: «π больше 3» и высказывание «π меньше 4». Можно организовывать новое — сложное высказывание «π больше 3 и π меньше 4». Высказывание «если π иррационально, то π² тоже иррационально» получается связыванием двух высказываний связкой «если — то». Наконец, мы можем получить из какого-либо высказывания новое — сложное высказывание — отрицая первоначальное высказывание.

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

Пусть даны два произвольных высказывания A и B.

1. Первая логическая операция над этими высказываниями — конъюнкция — представляет собой образование нового высказывания, которое будем обозначать A ∧ B и которое истинно тогда и только тогда, когда A и B истинны. В обычной речи этой операции соответствует соединение высказываний связкой «и».

Таблица истинности для конъюнкции:

A B A ∧ B
И И И
И Л Л
Л И Л
Л Л Л

2. Вторая логическая операция над высказываниями A и B — дизъюнкция, выражаемая в виде A ∨ B, определяется следующим образом: оно истинно тогда и только тогда, когда хотя бы одно из первоначальных высказываний истинно. В обычной речи эта операция соответствует соединению высказываний связкой «или». Однако здесь мы имеем не разделительное «или», которое понимается в смысле «либо-либо», когда A и B не могут быть оба истинны. В определении логики высказываний A ∨ B истинно и при истинности лишь одного из высказываний, и при истинности обоих высказываний A и B.

Таблица истинности для дизъюнкции:

A B A ∨ B
И И И
И Л И
Л И И
Л Л Л

3. Третья логическая операция над высказываниями A и B, выражаемая в виде A → B; полученное таким образом высказывание ложно тогда и только тогда, когда A истинно, а B ложно. A называется посылкой, B — следствием, а высказывание A → B — следованием, называемая также импликацией. В обычной речи эта операция соответствует связке «если — то»: «если A, то B». Но в определении логики высказываний это высказывание всегда истинно независимо от того, истинно или ложно высказывание B. Это обстоятельство можно кратко сформулировать так: «из ложного следует всё, что угодно». В свою очередь, если A истинно, а B ложно, то всё высказывание A → B ложно. Оно будет истинным тогда и только тогда, когда и A, и B истинны. Кратко это можно сформулировать так: «из истинного не может следовать ложное».

Таблица истинности для следования (импликации):

A B A → B
И И И
И Л Л
Л И И
Л Л И

4. Четвёртая логическая операция над высказываниями, точнее над одним высказыванием, называется отрицанием высказывания A и обозначается ~ A (можно встретить также употребление не символа ~, а символа ¬, а также верхнего надчёркивания над A). ~ A есть высказывание, которое ложно, когда A истинно, и истинно, когда A ложно.

Таблица истинности для отрицания:

A ~ A
Л И
И Л

5. И, наконец, пятая логическая операция над высказываниями называется эквивалентностью и обозначается A ↔ B. Полученное таким образом высказывание A ↔ B есть высказывание истинное тогда и только тогда, когда A и B оба истинны или оба ложны.

Таблица истинности для эквивалентности:

A B A → B B → A A ↔ B
И И И И И
И Л Л И Л
Л И И Л Л
Л Л И И И

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

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

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

Связка Обозначение Название операции
не отрицание
и конъюнкция
или дизъюнкция
если …, то… импликация
тогда и только тогда эквивалентность

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

Пример 1. Вычислите логические значения следующих высказываний:

1) (2 = 2) И (7 = 7);

2) Не(15 ;

3) («Сосна» = «Дуб») ИЛИ («Вишня» = «Клён»);

4) Не(«Сосна» = «Дуб»);

5) (Не(15 20);

6) («Глаза даны, чтобы видеть») И («Под третьим этажом находится второй этаж»);

7) (6/2 = 3) ИЛИ (7*5 = 20).

Решение.

1) Значение высказывания в первых скобках равно «истина», значение выражения во вторых скобках — также истина. Оба высказывания соединены логической операцией «И» (смотрим правила для этой операции выше), поэтому логическое значение всего данного высказывания — «истина».

2) Значение высказывания в скобках — «ложь». Перед этим зтим высказыванием стоит логическая операция отрицания, поэтому логическое значение всего данного высказывания — «истина».

3) Значение высказывания в первых скобках — «ложь», значение высказывания во вторых скобках — также «ложь». Высказывания соединены логической операцией «ИЛИ» и ни одно из высказываний не имеет значения «истина». Поэтому логическое значение всего данного высказывания — «ложь».

4) Значение высказывания в скобках — «ложь». Перед этим высказыванием стоит логическая операция отрицания. Поэтому логическое значение всего данного высказывания — «истина».

5) В первых скобках отрицается высказывание во внутренних скобках. Это высказывание во внутренних скобках имеет значение «ложь», следовательно, его отрицание будет иметь логическое значение «истина». Высказывание во вторых скобках имеет значение «ложь». Два этих высказывания соединены логической операцией «И», то есть получается «истина И ложь». Следовательно, логическое значение всего данного высказывания — «ложь».

6) Значение высказывания в первых скобках — «истина», значение высказывания во вторых скобках — также «истина». Два этих высказывания соединены логической операцией «И», то есть получается «истина И истина». Следовательно, логическое значение всего данного высказывания — «истина».

7) Значение высказывания в первых скобках — «истина». Значение высказывания во вторых скобках — «ложь». Два этих высказывания соединены логической операцией «ИЛИ», то есть получается «истина ИЛИ ложь». Следовательно, логическое значение всего данного высказывания — «истина».

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

1) «Пользователь не зарегистрирован»;

2) «Сегодня воскресенье и некоторые сотрудники находятся на работе»;

3) «Пользователь зарегистрирован тогда и только тогда, когда отправленные пользователем данные признаны годными».

Решение.

1) p — одиночное высказывание «Пользователь зарегистрирован», логическая операция: ;

2) p — одиночное высказывание «Сегодня воскресенье», q — «Некоторые сотрудники находятся на работе», логическая операция: ;

3) p — одиночное высказывание «Пользователь зарегистрирован», q — «Отправленные пользователем данные признаны годными», логическая операция: .

Решить примеры на логику высказываний самостоятельно, а затем посмотреть решения

Пример 3. Вычислите логические значения следующих высказываний:

1) («В минуте 70 секунд») ИЛИ («Работающие часы показывают время»);

2) (28 > 7) И (300/5 = 60);

3) («Телевизор — электрический прибор») И («Стекло — дерево»);

4) Не((300 > 100) ИЛИ («Жажду можно утолить водой»));

5) (75 < 81) → (88 = 88).

Правильное решение и ответ.

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

1) «Если часы неправильно показывают время, то можно невовремя прийти на занятия»;

2) «В зеркале можно увидеть своё отражение и Париж — столица США»;

3) Не «дуб — дерево».

Правильное решение и ответ.

Пример 5. Определите логическое значение выражения

(p → q) ↔ (r → s),

если

p = «278 > 5»,

q = «Яблоко = Апельсин»,

p = «0 = 9»,

s = «Шапка покрывает голову».

Правильное решение и ответ.

Формулы логики высказываний

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

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

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

p, q, r, …, p1, q1, r1, …

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

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

~, ∧, ∨, →, ↔,

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

Понятие формулы логики высказываний определим следуюшим образом:

1) элементарные формулы (атомы) являются формулами логики высказываний;

2) если A и B — формулы логики высказываний, то ~A, (A ∧ B), (A ∨ B), (A → B), (A ↔ B) тоже являются формулами логики высказываний;

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

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

Пример 6. Пусть p — одиночное высказывание (атом) «Все рациональные числа являются действительными», q — «Некоторые действительные числа — рациональные числа», r — «некоторые рациональные числа являются действительными». Переведите в форму словесных высказываний следующие формулы логики высказываний:

1) ;

2) ;

3) ;

4) ;

5) ;

6) .

Решение.

1) «нет действительных чисел, которые являются рациональными»;

2) «если не все рациональные числа являются действительными, то нет рациональных чисел, являющихся действительными»;

3) «если все рациональные числа являются действительными, то некоторые действительные числа — рациональные числа и некоторые рациональные числа являются действительными»;

4) «все действительные числа — рациональные числа и некоторые действительные числа — рациональные числа и некоторые рациональные числа являются действительными числами»;

5) «все рациональные числа являются действительными тогда и только тогда, когда не имеет место быть, что не все рациональные числа являются действительными»;

6) «не имеет места быть, что не имеет место быть, что не все рациональные числа являются действительными и нет действительных чисел, которые являются рациональными или нет рациональных чисел, которые являются действительными».

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

Решение. Составление таблицы истинности начинаем с записи значений («истина» или «ложь») для одиночных высказываний (атомов) p, q и r. Все возможные значения записываются в восемь строк таблицы. Далее, определяя значения операции импликации, и продвигаясь вправо по таблице, помним, что значение равно «лжи» тогда, когда из «истины» следует «ложь».

p q r f
И И И И И И И И
И И Л И И И Л И
И Л И И Л Л Л Л
И Л Л И Л Л И И
Л И И Л И Л И И
Л И Л Л И Л И Л
Л Л И И И И И И
Л Л Л И И И Л И

Заметим, что никакой атом не имеет вида ~A, (A ∧ B), (A ∨ B), (A → B), (A ↔ B). Такой вид имеют сложные формулы.

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

1) в сложной формуле будем опускать внешнюю пару скобок;

2) упорядочим знаки логических операций «по старшинству»:

↔, →, ∨, ∧, ~ .

В этом списке знак ↔ имеет самую большую область действия, а знак ~ — самую маленькую. Под областью действия знака операции понимаются те части формулы логики высказываний, к которым применяется (на которые действует) рассматриваемое вхождение этого знака. Таким образом, можно опускать во всякой формуле те пары скобок, которые можно восстановить, учитывая «порядок старшинства». А при восстановлении скобок сначала расставляются все скобки, относящиеся ко всем вхождениям знака ~ (при этом мы продвигаемся слева направо), затем ко всем вхождениям знака ∧ и так далее.

Пример 8. Восстановите скобки в формуле логики высказываний B ↔ ~ C ∨ D ∧ A.

Решение. Скобки восстанавливаются пошагово следующим образом:

B ↔ (~ C) ∨ D ∧ A

B ↔ (~ C) ∨ (D ∧ A)

B ↔ ((~ C) ∨ (D ∧ A))

(B ↔ ((~ C) ∨ (D ∧ A)))

Не всякая формула логики высказываний может быть записана без скобок. Например, в формулах А → (B → C) и ~ (A → B) дальнейшее исключение скобок невозможно.

Тавтологии и противоречия

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

Так как истинность или ложность сложных высказываний зависит лишь от значений, а не от содержания высказываний, каждому из которых соответствует определённая буква, то проверку того, является ли данное высказывание тавтологией, можно подставить следующим способом. В исследуемом выражении на место букв подставляются значения 1 и 0 (соответственно «истина» и «ложь») всеми возможными способами и с использованием логических операций вычисляются логические значения выражений. Если все эти значения равны 1, то исследуемое выражение есть тавтология, а если хотя бы одна подстановка даёт 0, то это не тавтология.

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

Противоположный смысл имеет логическое противоречие. Если все значения высказываний равны 0, то выражение есть логическое противоречие.

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

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

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

Решение. Составляем таблицу истинности:

И И И И И
И Л Л Л И
Л И Л И И
Л Л Л Л И

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

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

Решение. Составляем таблицу истинности:

И И И И И И
И И Л И Л Л
И Л И Л И И
И Л Л Л Л И
Л И И Л И И
Л И Л Л Л И
Л Л И Л И И
Л Л Л Л Л И

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

Заставляем компьютер понимать «если …, то…»

То, что мы называем логическими операциями, впервые появилось предположительно в Древней Греции для доказательства философских постулатов. А в наше время логические операции наиболее широко применяются в компьютерной технике. Но при всём этом компьютер «не умеет» выполнять логическую операцию импликации. Она компьютеру «не понятна». Есть, однако, способ заставить компьютер понимать условие «если …, то», соответствующее, как известно, импликации. Для этого вместо составного оператора «если p, то q» нужно использовать составной оператор «не p или q». То есть, вместо .

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

И И И
И Л Л
Л И И
Л Л И

Пример 11. Перепишите формулу логики высказываний без использования импликации и эквиваленции, пользуясь тождеством и законами де Моргана:

Решение.

Заменяем импликацию между двумя парами скобок, отрицая самый левый знак отрицания:

Убираем эквиваленцию между p и q и между q и не r:

Используя закон де Моргана, немного упрощаем и окончательно получаем:

Посылки и выводы. Валидный и не валидный аргумент

Пусть есть высказывания, которые можно назвать посылками. Пусть также есть высказывание, которое можно назвать выводом. Словосочетание «можно назвать» используется при условии, что посылки связываются с выводом. То есть, из посылок логически следует вывод. Тогда, если посылки имеют значения «истина» и вывод тоже имеет значение «истина», то аргумент является валидным. Если же посылки имеют значения «истина», а вывод имеет значение «ложь», то аргумент не является валидным. Синонимы понятия «валидность» (в рассматриваемом здесь значении) — «логическая правильность», «резонность».

Пример валидного аргумента:

  • Посылка. A и B — программисты
  • Посылка. A и B разрабатывают программы для бухгалтеров
  • Вывод. Есть программисты, которые разрабатывают программы для бухгалтеров

То есть, из посылок логически следует вывод.

Пример не валидного аргумента:

  • Посылка. Запись числа может содержать запятую
  • Посылка. В предложении может быть запятая
  • Вывод. Есть числа, которые называются предложениями

То есть, из посылок логически не следует вывод.

Пример 12. Проверьте валидность аргумента, если

  • Посылка.
  • Посылка.
  • Вывод.

Решение. Составляем таблицу истинности:

И И Л И И И
И Л Л Л Л И
Л И И И И Л
Л Л И И И И

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

Применение логики высказываний в информатике и программировании

Логика высказываний применяется в информатике и программировании в виде объявления логических переменных и присвоения им логических значений «ложь» или «истина», от которых зависит ход дальнейшего исполнения программы. В небольших программах, где задействована лишь одна логическая переменная, этой логической переменной часто даётся имя, например, «флаг» («flag») и подразумевается, что «флаг поднят», когда значение этой переменной — «истина» и «флаг опущен», когда значение этой переменной — «ложь». В программах большого объёма, в которых несколько или даже очень много логических переменных, от профессионалов требуется придумывать имена логических переменных, имеющих форму высказываний и смысловую нагрузку, отличающую их от других логических переменных и понятных другим профессионалам, которые будут читать текст этой программы.

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

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

Сложное высказывание

Определение 1

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

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

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

Высказывание является простым, если в нём в качестве своих частей нет других высказываний.

Готовые работы на аналогичную тему

  • Курсовая работа Сложное высказывание 470 руб.
  • Реферат Сложное высказывание 270 руб.
  • Контрольная работа Сложное высказывание 240 руб.

Получить выполненную работу или консультацию специалиста по вашему учебному проекту Узнать стоимость

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

Замечание 1

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

Способы построения базовых сложных высказываний

Отрицание (инверсия)

В русском языке этой логической связке соответствует частица НЕ (иногда нужно применить оборот «неверно что…»).

Определение 2

Отрицание (инверсию) можно представить в форме таблицы истинности, в которой «$1$» означает «истинно» и «$0$» – «ложно».


Рисунок 1.

Конъюнкция (логическое умножение)

Определение 3

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

Конъюнкция истинна тогда и только тогда, когда все её составляющие являются истинными; в противном случае вся конъюнкция ложна.

Составляющее конъюнкцию высказывание $A$ может быть либо истинно, либо ложно, то же самое можно сказать и о высказывании $B$. Возможны четыре варианта комбинаций значений истинности для этих высказываний.

Если конъюнкцию обозначить символом «&», то таблица истинности для конъюнкции будет выглядеть следующим образом


Рисунок 2.

Дизъюнкция

Определение 4

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

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

В первом случае «или» называется неисключающим. Такая дизъюнкция двух высказываний истинна тогда, когда истинно хотя бы одно из этих высказываний. Во втором случае исключающая дизъюнкция двух высказываний истинна тогда, когда истинна только одна из её составляющих. Символом ∪ обозначим дизъюнкцию в неисключающем смысле, для исключающего «или» (дизъюнкции в исключающем смысле) будем использовать символ $Ủ$.

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


Рисунок 3.

Связка «или» в логике и математике всегда употребляется в неисключающем значении.

Импликация

Определение 5

Импликация – сложное высказывание, которое формулируется с помощью связки «если …, то …» и устанавливает, что одно событие, состояние и т.п. является в том или ином смысле основанием или условием для того, чтобы выполнилось другое. Например, сложное высказывание «Нет дыма без огня» состоит из двух простых высказываний «Есть огонь» и «Есть дым» и преобразуется в высказывание «Если есть огонь, то есть дым»; или «Если сумма цифр числа делится на $3$, то и само число делится на $3$» и т.п.

Условное высказывание состоит из двух простых высказываний. То, что стоит за словом «если», называется предпосылкой, основанием, условием, или антецедентом (предыдущим); высказывание, которое идёт после слова «то», называется следствием, выводом, или консеквентом (последующим).

Условное высказывание в логике называется импликацией.

Импликация истинна в трех случаях:

  1. когда истинны и ее основание, и ее следствие;

  2. когда условие ложно, а следствие истинно;

  3. когда и предпосылка, и вывод ложны.

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

Обозначим импликацию символом $→$ и построим таблицу истинности для импликации:


Рисунок 4.

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

Эквивалентность

Определение 6


Рисунок 5.

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

А.В.Чагров

ФОРМАЛЬНАЯ ПРОПОЗИЦИОНАЛЬНАЯ ЛОГИКА А.ВИССЕРА И ЕЕ РАСШИРЕНИЯ*

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

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

* Работа выполнена при поддержке гранта РФФИ № 03-06-80115.

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

Однако и обратная проблематика — непосредственное описание логических систем с сильными пропозициональными связками без того, чтобы считать их фрагментами систем с более богатым по выразительным свойствам языком — достойна внимания. Здесь уместно вспомнить параллельную, но в определенном смысле крайнюю ситуацию, выраженную где-то встречавшимися автору словами вроде «Да, натуральные числа выразимы в теории множеств, но вряд ли исследователя свойств натуральных чисел может это порадовать, поскольку теория множеств нисколько не помогает изучать свойства натуральных чисел»; более того, можно добавить, что погружение теории натуральных чисел в теорию множеств отчасти и вредно, поскольку создает опасную иллюзию, что для натуральных чисел есть по крайней мере стандартная (естественная!) модель (верить или нет в непротиворечивость представлений о ней — важный, но другой вопрос), в то время как для теории множеств до сих пор не предъявлено какой-либо убедительной естественной модели (и вопрос о непротиворечивости здесь существенно более труден).

Здесь мы обратимся к не так давно созданной А.Виссером логической системе, названной им FPL (от formal prepositional logic, что ввиду неинформативности не вполне удачно, но можно было бы считать эту аббревиатуру сокращением названия fixed point logic, что, кстати, соответствовало бы и названию статьи А.Виссера — A prepositional logic with explicit fixed points). Эта система была сформулирована им в виде исчисления натурального вывода. По сути она получается ослаблением интуиционистской системы путем удаления правила modus ponens (в результате получается система, названная А.Виссером BPL от basic proposi-tional logic), а затем усилением путем включения в систему нового, ни классически, ни интуиционистски не приемлемого правила,

позволяющего переходить от формулы вида ((L ^L) ^ A) ^ A к формуле (_L ^L) ^ A. Это последнее правило очень похоже на правило Леба в модальной логике доказуемости GL, поэтому и мы вслед за А.Виссером будем так его называть.

Хотя вопросы построения исчислений непосредственно не входят в круг интересующих нас здесь задач, отметим, что оба исчисления — и BPL, и FPL — обладают весьма необычными свойствами по отношению к столь привычному логикам правилу modus ponens. Если добавить modus ponens к BPL, получится исчисление, аксиоматизирующее интуиционистскую пропозициональную логику, а если к FPL — получится противоречивое исчисление, то есть исчисление, в котором выводимы все формулы. Это отчасти связано с тем, что в обоих исчислениях есть правило введения импликации («теорема о дедукции»), но не выводима формула, формально выражающая modus ponens — A & (A ^ B) ^ B. С другой стороны, обе логики как множества формул, выводимых в исчислениях BPL и FPL, замкнуты относительно правила modus ponens. Это необычное свойство приводит нас к вопросу: какое множество формул называть расширением логики BPL и/или FPL. Скажем, в случае интуиционистской логики ответ дается обычно так: расширением ее является всякое множество формул, содержащее все интуиционистски выводимые формулы и замкнутое относительно правил подстановки и modus ponens. Но ведь в случае интуиционистской логики таких необычных свойств правило modus ponens не имеет.

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

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

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

попал некоторый мир, то и все достижимые из него также попадают. Значение формулы в мире (отношение «в мире а истинна формула ф») при данной оценке задается индукцией по построению формулы: константа ^ («ложь») не является истинной ни в одном мире; в мире а истинна пропозициональная переменная p, если оценкой переменной p сопоставляется множество, содержащее мир а; конъюнкция истинна в мире а, если в этом мире истинны оба конъюнктивных члена; дизъюнкция истинна в мире а, если в этом мире истинен хотя бы один из дизъюнктивных членов; импликация истинна в мире а, если для всякого мира ß, достижимого из а, из того, что в ß истинна посылка импликации, следует, что в ß истинно и заключение этой импликации. (Отметим, что специфика шкалы здесь проявляется только в пункте об импликации.) Наконец, формула считается истинной в шкале, если она истинна в каждой точке этой шкалы при любой оценке.

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

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

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

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

Теперь в данной статье определяем расширение FPL (другими словами, логикой, расширяющей FPL) как множество формул, истинных в некотором классе обобщенных шкал, не содержащих бесконечных возрастающих цепей, замкнутое относительно modus ponens. Несложно понять, что если такое расширение непротиворечиво (то есть не есть множество всех формул), то задающий его класс обобщенных шкал бесконечен или содержит бесконечные шкалы. Всякое расширение FPL можно «аксиоматизировать» следующим образом: если Г — некоторое множество формул, то FPL + Г — минимальное по включению расширение, содержащее Г (множество дополнительных аксиом).

Для сравнения заметим, что если в предыдущем абзаце мы используем обобщенные интуиционистские шкалы, которые получатся наложением требования рефлексивности вместо иррефлексивности, то замкнутости относительно modus ponens можно будет не требовать, поскольку она будет выполняться автоматически, причем заданными окажутся в точности все суперинтуиционистские логики. Это отчасти оправдывает принятое нами здесь определение расширение FPL.

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

(Напомним, что ширина шкалы — это максимальная мощность множеств, состоящих из попарно несравнимых миров.)

С расширениями ЕРЬ ситуация иная.

Теорема 1. Существует континуум расширений ЕРЬ формулами от одной переменной.

Для доказательства можно взять формулы фп = ((1^1)п+11 & рт ^ (1^1)п1) V ((1^1)и+11 ^ (1^1)п1 V р), где формулы (1^1)т1 определяются индукцией по т:

Небольшой модификацией приведенного доказательства -нужно брать логики, определяемые классами шкал вида {¥п : п из I}, а с помощь формул фп обосновывать их различие при различных индексных множествах I — доказывается

Теорема 2. Существует континуум расширений ЕРЬ ширины не более 2.

В этом, в общем-то, нет ничего удивительного. В суперинтуиционистских логиках справедлив аналог теоремы 2. Однако семейство суперинтуиционистских логик ширины 1 (логики ширины 1 называют линейными, а в случае суперинтуиционистских логик еще и цепными) счетно, в то время как для расширений ЕРЬ справедлива

Теорема 3. Существует ровно одно непротиворечивое линейное расширение ЕРЬ.

iНе можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

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

Теперь обратимся к проблеме полноты по Крипке. Как уже было сказано, всякая суперинтуиционистская логика конечной ширины обладает полнотой по Крипке. Однако для расширений ЕРЬ оказывается верной

Теорема 4. Существуют неполные по Крипке расширения ЕРЬ.

Доказательство основано на примере, обнаруженном авторами : оказалось, что существуют табличные расширения, которые не полны по Крипке. Это выглядит довольно удивительно ввиду того, что в изучавшихся до сих пор классах неклассических логик, будь то суперинтуиционистские, модальные, многомодальные, всякая табличная логика полна по Крипке. Конечно, в силу отмеченного выше обстоятельства логика не замкнута относительно правила modus ponens, однако с помощью нехитрого приема, по сути использованного в доказательстве теорем 1 и 2, этого обстоятельства удается избежать (потеряв, конечно, табличность). Прием этот состоит в том, что, скажем, для доказательства теоремы 2 нам было бы достаточно рассматривать варианты шкал вида Fn, в которых отсутствуют миры n + 2, n + 3, n + 4 и т.д.; их введение и обеспечивает замкнутость определяемых в том доказательстве логик относительно modus ponens.

Обратимся, однако, к примеру неполной логики. Он задается следующей обобщенной шкалой: в шкале F0 в качестве фиксированного семейства наследственных множеств берутся все, кроме множества {0′} (то есть множества, состоящего из двойника нуля); То, что это обобщенная шкала, проверятся рутинными вычислениями. Пусть L — логика, задаваемая этой шкалой. Теперь обратим внимание, что в этой обобщенной шкале опровергается формула ф0 (а потому ф0 не принадлежит L), для опровержения которой в обобщенной шкале и, в частности, в шкале Крипке необходимо наличие мира, из которого достижимы два различных мира, из которых ничего не достижимо, однако формулу (p ^ q) v (q ^ p), как легко убедиться, опровергнуть невозможно, а значит логике L она принадлежит. Теперь допустим, что логика L полна по Крипке. Тогда, чтобы опровергать не принадлежащую ей формулу ф0, класс ее шкал Крипке должен содержать шкалу, в которой есть мир, из которого достижимы два разных мира, из которых ничего не достижимо. Назовем эти три мира соответственно а, b, c. Теперь взяв в качестве оценки переменной p множество {b}, а в качестве оценки q — множество {с}, мы получаем, что формула (p ^ q) v (q ^ p) опровергается в мире а. Получили противоречие, которое показывает, что допущенное нами неверно, то есть на самом деле логика L полной по Крипке не является.

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

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

ЛИТЕРАТУРА

[ad01]

Рубрики: Разное

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *