МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ
БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
ВВЕДЕНИЕ В ЛОГИКУ ВЫСКАЗЫВАНИЙ
Учебно-методическое пособие
Составитель
А. В. Арапов
Воронеж
Издательский дом ВГУ
2014
Стр.1
Введение
Логика высказываний (пропозициональная логика) работает с пропозициями
(высказываниями) и их взаимоотношениями. Затруднительно дать
однозначное определение пропозиции. Термин восходит к лат. propositio,
первоначально обозначавшему в логике суждение. На формирование современного
понимания термина в разные периоды оказывали влияния исследования
в логике, семиотике, лингвистике. В классической логике пропозиция
соответствовала определенной форме мысли, понятию суждения,
обладающее свойством выражать либо ложь, либо истину, отрицать или утверждать
что-либо о предметах действительности. Примеры таких суждений:
Этот снег белый, Сейчас Солнце светит. Позже под пропозицией стали
понимать «объективное содержание» мысли как выражение истинностного
значения коммуникативной цели высказывания. И наконец, было признано,
что пропозиция существует во всех видах предложений, за исключением
коротких восклицаний: «Ой!», «Ого!», и т. п. В настоящем пособии мы рассмотрим
базовые элементы пропозициональной логики: синтаксис пропозиций,
семантику пропозиций, логические свойства пропозиций и линейный
вывод.
Синтаксис пропозиций
В пропозициональной логике есть два типа высказываний – простые
высказывания и составные (сложные) высказывания. Простые высказывания
выражают простые факты. Составные высказывания выражают логические
отношения между простыми высказываниями, из которых они составлены.
Простые
высказывания в пропозициональной логике часто именуются
элементарными или атомарными высказываниями.
Составные высказывания образуются из простых высказываний с помощью
логических операторов (пропозициональных связок) и выражают
отношения между ними. Составные высказывания именуются также сложными
или молекулярными высказываниями. Пропозициональным словарем
именуется множество простых высказываний. Пропозициональным языком
именуется множество высказываний, которые могут быть образованы на
основе пропозиционального словаря.
Существуют пять типов составных высказываний: отрицание, конъюнкция,
дизъюнкция, импликация и эквивалентность.
Отрицание состоит из оператора ¬ и простого или составного высказывания,
именуемого объект. Отрицание именуется также негацией. Например,
если нам дано высказывание p, мы можем сформировать следующее
отрицание:
(¬p).
3
Стр.3
φ ψ φ ⇒ ψ
1 1 1
1 0 0
0 1 1
0 0 1
В разговорном языке смысл высказывания вида «Если А, то B» неясен.
Разумеется, высказывание «если А, то В» ложно, когда посылка А истинна,
а заключение В ложно. Однако в других случаях, при обычном употреблении
этой связки, мы не имеем вполне определенного истинностного
значения. Неясно, например, истинными или ложными следует считать высказывания:
(1)
Если 1+1 =2, то Париж есть столица Франции.
(2) Если 1+1 > 2, то Париж есть столица Франции.
(3) Если, Если 1+1 < 2, то Рим есть столица Франции
Смысл их неясен, поскольку мы привыкли к тому, что между посылкой
и заключением имеется определенная (обычно причинная) связь. В
пропозициональной логике высказывание «если А, то В» ложно тогда и
только тогда, когда истинно А и ложно В. Таким образом, высказывания (1)
– (3) будут считаться истинными.
Эквивалентность истинна в том и только в том случае, если значения
истинности обоих метапеременных совпадает, т.е. они обе истинны или
ложны.
φ ψ φ ⇔ ψ
1 1 1
1 0 0
0 1 0
0 0 1
Используя семантические определения данные выше, мы можем легко
оценить значение истинности любого высказывания, как простого, таки
составного, если даны значения истинности для его пропозициональных
констант. Техника следующая. Мы подставляем значения истинности на
место пропозициональных констант в нашем высказывании. Образуется
высказывание, состоящее из нолей, единиц и логических операторов. Затем
мы используем семантику операторов и определяем истинность каждой из
подформул. Мы повторяем эту процедуру до тех пор, пока не получим значение
истинности для высказывания в целом.
Рассмотрим, например, интерпретацию i, показанную ниже.
pi = 1
qi = 0
ri = 1.
6
Стр.6
Используя вышеприведенный метод, мы можем увидеть, что при интерпретации
i (p ∨ q) ∧ (¬q ∨ r) истинно.
(p ∨ q) ∧ (¬ q ∨ r)
(1 ∨ 0) ∧ (¬ 0 ∨ 1)
1 ∧ (¬ 0 ∨ 1)
1 ∧ (1 ∨ 1)
1 ∧ 1
1
Теперь рассмотрим интерпретацию j, определенную ниже:
pj = 1
qj = 1
rj = 0.
В этом случае, (p ∨ q) ∧ (¬q ∨ r) ложно.
(p ∨ q) ∧ (¬q ∨ r)
(1 ∨ 1) ∧ (¬1 ∨ 0)
1 ∧ (¬1 ∨ 0)
1 ∧ (0 ∨ 0)
1 ∧ 0
0
Используя эту технику, мы можем определить истинность произвольного
высказывания нашего языка. Сложность процедуры пропорциональна
длине высказывания.
Мы говорим, что при данной интерпретации высказывание выполнено
тогда и только тогда, когда оно истинно при данной интерпретации. Мы говорим,
что интерпретация фальсифицирует высказывание тогда и только
тогда, когда оно ложно при данной интерпретации. Множество высказываний
выполнено при данной интерпретации тогда и только тогда, когда оно
при ней выполнены все высказывания данного множества. Интерпретация
фальсифицирует множество высказываний тогда и только тогда, когда оно
фальсифицирует хотя бы одно высказывание из этого множества.
Логические свойства высказываний
Выказывание является тождественно-истинным (тавтологией) тогда и
только тогда, когда оно может быть выполнено при любой интерпретации.
Например, высказывание p ∨ ¬p является тождественно-истинным.
Высказывание является тождественно-ложным (противоречием) если
оно не может быть выполнено при любой интерпретации. Например, высказывание
p ⇔ ¬p тождественно-ложное. Независимо ль того, какую интерпретацию
мы возьмем, это высказывание всегда будет ложным.
Высказывание является необщезначимым тогда и только тогда, когда
существует такая интерпретация, при которой оно может быть выполнено и
такая интерпретация, при которой оно не может быть выполнено.
7
Стр.7
Эти три вида высказываний часто распределяются на три группы: выполнимые
высказывания и невыполнимые высказывания. К выполнимым
высказывания относятся: тавтологии и необщезначимые высказывания. К
невыполнимым относятся тождественно-ложные высказывания.
Логическое следование
Из множества высказываний Δ логически следует высказывание φ
(пишется Δ |= φ) в том и только в том случае, если при любой интерпретации,
при которой выполнено Δ, выполнено и φ
Например, высказывание (p ∨ q) логически следует из высказывания
p. Поскольку дизъюнкция истинна, если один из дизъюнктов истинен, то (p
∨ q) должно быть истинным, если p истинно. С другой стороны, высказывание
(p ∧ q) не следует из высказывания p. Конъюнкция истинна тогда и
только тогда, когда оба её конъюнкта являются истинными. Между тем q
может быть ложным. Разумеется, (p ∧ q) следует из любого множества высказываний
, содержащего и p и q .
Следование, о котором здесь говорится, является исключительно логическим.
Даже если из посылок логически не следует заключение, это не
означает, что заключение обязательно материально ложно. Это означает
лишь, что оно возможно ложно. Вновь рассмотрим случай o (p ∧ q). Хотя
это высказывание логически не следует из p, есть возможность, что истинны
и p и q и, следовательно (p ∧ q) истинно. Однако, логического следования
здесь нет, поскольку, есть также возможность, что q ложно и тогда (p ∧
q) ложно.
Следует иметь в виду, что логическое следование не то же самое, что
логическая эквивалентность, и оно не является аналогом арифметического
равенства. Из высказывания p логически следует (p ∨q), но из (p ∨ q) не
следует p.
Один из способов определить следует ли из данного множества посылок
некоторое заключение, состоит в построении таблицы истинности. Этот
метод называется табличным методом. Он состоит из следующих шагов.
(1)Мы формируем таблицу истинности из простых высказываний
данного языка и добавляем столбец для посылок и столбец для заключения.
(2) Мы определяем истинность посылок. (3) Мы определяем истинность заключения.
(4) Мы сравниваем значения истинности посылок и заключения.
Если в каждой строке, в которой все посылки истинны, истинно и заключение,
то заключение логически следует из посылок.
Рассмотрим вопрос о том, в каком случае из множества пропозиций
{p, q} логически следует (p∧ q). Мы составляем таблицу, как и в предыдущих
случаях, однако в этот раз мы имеем две посылки. Только при одной
интерпретации истинны обе посылки и мы обнаруживаем, что при этой интерпретации
истинно и заключение. Следовательно логическое следование
в данном случае имеет место.
8
Стр.8