новая папка 1 / 298007

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

ВВЕДЕНИЕ В ЛОГИКУ ВЫСКАЗЫВАНИЙ

Учебно-методическое пособие

Составитель А. В. Арапов

Воронеж Издательский дом ВГУ

2014

Утверждено научно-методическим советом Института заочного экономического образования 10 апреля 2014 г., протокол № 10-05

Рецензент профессор кафедры культурологии В. В. Варава

Учебно-методическое пособие подготовлено на кафедре онтологии и теории познания факультета философии и психологии Воронежского государственного университета.

Рекомендуется для студентов Института заочного экономического образования, обучающихся по направлению 080050 – Бизнес-информатика

Для направления 080050 – Бизнес-информатика

2

Введение

Логика высказываний (пропозициональная логика) работает с пропозициями (высказываниями) и их взаимоотношениями. Затруднительно дать однозначное определение пропозиции. Термин восходит к лат. propositio, первоначально обозначавшему в логике суждение. На формирование современного понимания термина в разные периоды оказывали влияния исследования в логике, семиотике, лингвистике. В классической логике пропозиция соответствовала определенной форме мысли, понятию суждения, обладающее свойством выражать либо ложь, либо истину, отрицать или утверждать что-либо о предметах действительности. Примеры таких суждений: Этот снег белый, Сейчас Солнце светит. Позже под пропозицией стали понимать «объективное содержание» мысли как выражение истинностного значения коммуникативной цели высказывания. И наконец, было признано, что пропозиция существует во всех видах предложений, за исключением коротких восклицаний: «Ой!», «Ого!», и т. п. В настоящем пособии мы рассмотрим базовые элементы пропозициональной логики: синтаксис пропозиций, семантику пропозиций, логические свойства пропозиций и линейный вывод.

Синтаксис пропозиций

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

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

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

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

Отрицание состоит из оператора ¬ и простого или составного высказывания, именуемого объект. Отрицание именуется также негацией. Например, если нам дано высказывание p, мы можем сформировать следующее отрицание:

(¬p).

3

Конъюнкция – это последовательность высказываний, разделенная оператором и заключенная в скобки, как показано ниже. Образующие её высказывания именуются членами конъюнкции (или конъюнктами). Например, мы можем составить конъюнкцию p и q следующим образом:

(p q).

Дизъюнкция – это последовательность высказываний, разделенная оператором и заключенная в скобки. Образующие её операторы именуются членами дизъюнкции (или дизъюнктами). Например, мы можем составить дизъюнкцию p и q следующим образом:

(p q).

Импликация – это последовательность высказываний, разделенная оператором и заключенная в скобки. Высказывание слева от оператора именуется антецендентом или условием, а высказывание справа – консеквентом или следствием. Например, мы можем составить импликацию p и q следующим образом:

(p q).

Эквивалентность или равносильность – это последовательность высказываний, разделенная оператором . Например, мы можем составить эквивалентность из p и q следующим образом:

(p q).

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

((p q) r).

Семантика пропозиций

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

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

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

но p, q и r:

pi = 1 qi = 0 ri = 1.

Ниже показано другая интерпретация для того же самого языка. pi = 0

qi = 0 ri = 1.

4

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

Если значение истинности высказывания – истина, то значение истинности его отрицания – ложь. Если значение истинности высказывания – ложь, то значение истинности для его отрицания – истина.

Значение истинности конъюнкции – истина, в том и только в том случае, если значение истинности обоих её членов – истина. В любом другом случае, значение истинности конъюнкции – ложь.

φψ φ ψ

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

Вданном случае оператор интерпретируется как соединительное или. Такая конъюнкция именуется нестрогой конъюнкцией.

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

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

ся материальной импликацией.

5

В разговорном языке смысл высказывания вида «Если А, то B» неясен. Разумеется, высказывание «если А, то В» ложно, когда посылка А истинна, а заключение В ложно. Однако в других случаях, при обычном употреблении этой связки, мы не имеем вполне определенного истинностного значения. Неясно, например, истинными или ложными следует считать высказывания:

(1)Если 1+1 =2, то Париж есть столица Франции.

(2)Если 1+1 > 2, то Париж есть столица Франции.

(3)Если, Если 1+1 < 2, то Рим есть столица Франции

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

– (3) будут считаться истинными.

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

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

Рассмотрим, например, интерпретацию i, показанную ниже. pi = 1

qi = 0 ri = 1.

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

Эти три вида высказываний часто распределяются на три группы: выполнимые высказывания и невыполнимые высказывания. К выполнимым высказывания относятся: тавтологии и необщезначимые высказывания. К невыполнимым относятся тождественно-ложные высказывания.

(пишется |= φ) в том и только в том случае, если при любой интерпретации, при которой выполнено , выполнено и φ

Например, высказывание (p q) логически следует из высказывания p. Поскольку дизъюнкция истинна, если один из дизъюнктов истинен, то (pq) должно быть истинным, если 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

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

В завершении этого параграфа мы рассмотрим связь между логическим следованием и выполнимостью. Эта связь формулируется в виде Тео-

Доказательство: Предположим |= φ. Если при некоторой интерпретации истинно, то при этой интерпретации φ также истинно. Но тогда при

при этой интерпретации φ будет истинно. Следовательно, |= φ. Эта теорема используется в различных методах логического вывода.

Линейные выводы

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

Схема – это выражение, в котором используются метапеременные вместо различных частей этого выражения. Например, следующее выражение является схемой с метапеременными φ and ψ:

φ ψ.

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

9

φ ψ

Φ

______

ψ

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

p q

P

______

q

Если метапеременная появляется более одного раза, в примере каждый раз должно подставляться одно и то же высказывание. Например, в приведенном выше случае удаления импликации будет недопустимым в одном случае заменить φ одни высказыванием, а в другом – другим.

Метапеременные могут быть заменены как простыми высказываниями, так и составными. Ниже приведен пример, в котором метапеременные заменены сложными высказываниями.

(p q) (q r)

(p q)

__________________

(q r)

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

Правила вывода, которые не содержат посылок, называются схемами аксиом. Существует ряд наборов аксиом. Рассмотрим набор схем, именуе-

мый схемы аксиом Мендельсона.

Схема создания импликации (IC) в сочетании с удалением импликации позволяет нам выводить импликации

φ (ψ φ)

10