Тема 5. Использование логических законов при работе с информацией

Задачи: 1) определять простые и сложные высказывания, выявлять в сложных высказываниях… 2) осуществлять перевод с естественного языка на формальный и сформального на естественный язык;

Задания и вопросы для подготовки к занятию

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

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

3. Выделите союзы в следующих выражениях и объясните, что они обозначают:

А) если в четырёхугольнике: 1) противоположные стороны равны или 2) две противоположные стороны равны и параллельны, то такой четырёхугольник есть параллелограмм;

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

Теоретические сведения и образцы решения основных типов задач

Высказывания

Любая научная теория воспринимается нами как некоторая система утверждений. Истинность каждого из них, вообще говоря, нуждается в доказательстве. В… Определение 1. Высказыванием называется предложение, которое может быть либо…

Примеры.

1. Предложение «Снег – белый» есть истинное высказывание.

2. Предложение «Волга впадает в Средиземное море» – ложное высказывание.

3.Предложение «2+2=10» – ложное высказывание.

Далеко не всякое предложение является высказыванием. В частности, вопросительные и восклицательные предложения не относятся к высказываниям. Например, по поводу предложения «Который час?» не имеет смысла ставить вопрос, истинно оно или ложно; то же самое относится, скажем, к предложению «Мойте руки перед едой!» Не являются высказываниями и такие предложения, которые служат определениями чего-либо, например: «Трапецией называется четырехугольник, две стороны которого параллельны».

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

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

В дальнейшем будем обозначать высказывания заглавными буквами латинского алфавита: P, Q, R и т.д.

2. Значение истинности высказывания

Условимся каждому истинному высказыванию сопоставлять число 1, а ложному – число 0. Иначе говоря, введем на множестве всех высказываний функцию , которая принимает значения 1 или 0 в зависимости от того, истинно высказывание Р или ложно:

Определение 2. Число называется значением истинности высказывания Р.

Так, для высказывания Р: «В неделе 7 дней» , а для высказывания Q: «Волга впадает в Средиземное море» .

Операции над высказываниями

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

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

Таблица 1

Условные обозначения логических связок

1. Отрицание высказывания Определение 1. Отрицанием высказывания Р называется новое высказывание,… Иначе говоря, значения истинности высказываний Р и связаны между собой, как указано в следующей таблице: …

Примеры.

1. Высказывание «Число 2 четное и простое» является конъюнкцией высказываний: «Число 2 четное» и «Число 2 простое». Так как оба последних высказывания истинны, то истинна и их конъюнкция.

2. Высказывания «2 меньше 5» и «5 меньше 10» истинны, поэтому истинна и их конъюнкция «2 меньше 5 и 5 меньше 10». Последнее высказывание записывают обычно так: «2<5<10».

3. Дизъюнкция высказываний

Определение 3. Дизъюнкцией высказываний Р и Q называется новое высказывание, обозначаемое (читается «Р или Q»), которое истинно в тех случаях, если истинно хотя бы одно из высказываний Р или Q, и ложно, если ложны оба высказывания Р и Q.

Значение истинности высказывания связано со значениями истинности высказываний Р и Q с помощью таблицы:

Эта таблица называется таблицей истинности для дизъюнкции.

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

Примеры.

1. Высказывание «В неделе 10 дней или в году 12 месяцев» является дизъюнкцией двух высказываний: «В неделе 10 дней» и «В году 12 месяцев». Несмотря на кажущуюся странность такого высказывания, мы все же признаем его истинным, поскольку истинно одно из составляющих его высказываний («В году 12 месяцев»).

2. Высказывание «2<3» является дизъюнкцией высказываний «2<3» и «2=3», из которых первое истинно, а второе ложно. Следовательно, истинна и сама дизъюнкция.

4. Импликация высказываний

Определение 4. Импликацией высказываний Р и Q называется высказывание, обозначаемое (читается: «Если Р, то Q», или «Из Р следует Q», или «P влечет за собой Q»), которое ложно лишь в том случае, если Р истинно, a Q ложно.

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

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

Заметим, что при рассмотрении импликации P=>Q высказывание Р называют посылкой (или условием) импликации, а высказывание Q – ее заключением (или следствием).

Примеры.

1. Высказывание «Если Земля круглая, то » является импликацией высказываний «Земля круглая» и «». Оно истинно, так как истинны оба последних высказывания.

2. Высказывание «Если , то число 5 – простое» есть импликация высказываний «» и «5 – простое». Оно истинно, поскольку посылка «» – Ложное высказывание.

5. Эквивалентность высказываний

Определение 5. Эквивалентностью (или эквиваленцией) высказываний Р и Q называется новое высказывание, обозначаемое (читается «P эквивалентно Q», или «P тогда и только тогда, когда Q»), которой истинно в том и только в том случае, если Р и Q одновременно Истинны или одновременно ложны.

Таблица истинности для эквивалентности выглядит следующим образом:

Примеры.

1.Высказывание «2 2 = 4» тогда и только тогда, когда Земля – шар" представляет собой эквиваленцию двух высказываний: «2 2 = 4» и «Земля – шар». Оно истинно, поскольку истины оба этих высказывания.

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

6. Логические операции как операции на множестве

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

над ними с помощью таблицы

Аналогичные замечания можно сделать и по отношению к остальным логическим операциям.

Например, и т. д.

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

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

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

Примеры.

1. Доказать равносильность формул и .

Для каждой из данных формул составим таблицу истинности:

	Y				Y

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

2. Доказать равносильность формул и .

Разумеется, можно сравнить таблицы истинности данных формул! Однако можно рассуждать и так: формула ложна лишь в случае Х= 1, Y = 0, а формула – лишь в случае X = О, Y = 0, т. е. при Х= 1, Y = 0. Таким образом, обе формулы ложны или истинны одновременно.

Целый ряд равносильностей можно получить, исходя из приведенных в п. 3 тавтологий. Например, формулы и равносильны, поскольку формула является тавтологией (см. тавтологии 4°).

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

Задания для работы на занятии

1. Определить, является ли данная последовательность формулой:

1.1	1.6
1.2	1.7
1.3	1.8
1.4	1.9
1.5	1.10

2. Построить таблицы истинности для формул:

2.1

2.2

2.3

2.4

2.5

2.6

2.7

2.8

2.9

2.10

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

3.1

3.2

3.3

3.4

3.5

3.6

3.7

3.8

3.9

3.10

1. Доказать эквивалентности

4.1

4.2

4.3	4.7
4.4	4.8
4.5	4.9
4.6	4.10

5. Для какого из указанных значений числа Х истинно выражение:

5.1

1) 1	3) 3
2) 2	4) 4

5.2

1) 1	3) 3
2) 2	4) 4

5.3

1) 1	3) 3
2) 2	4) 4

5.4

1) 5	3) 3
2) 6	4) 4

5.5

1) 7	3) 9
2) 8	4) 10

5.6

1) 7	3) 9
2) 4	4) 2

5.7

1) 3	3) 7
2) 4	4) 2

5.8

1) 5	3) 11
2) 9	4) 4

5.9

1) 8	3) 10
2) 6	4) 4

5.10

1) 0	3) 7
2) 2	4) 4

Контрольные вопросы

1. Что изучает математическая логика?

2.Как определить, что предложение является высказыванием?

3. Каким союзам русского языка соответствуют операции отрицания, конъюнкции, дизъюнкции, импликации, эквиваленции?

4. Какие обозначения соответствуют союзам русского языка: … тогда и

только тогда, когда …; и; или; если …, то…; не?

5. Какие значения истинности принимают операции отрицания, конъюнкции, дизъюнкции, импликации, эквиваленции в зависимости от значений переменных?

6. Как формулируется алгоритм перевода с естественного языка на формальный?

7. Каким образом осуществить перевод с формального языка на естественный?

8. Как доказать логический закон?

9. Какого типа задачи и каким образом решаются с помощью таблиц истинности?

Библиографический список

2. Козлов В. Н. Математика и информатика / В.Н. Козлов. – СПб.: Питер, 2004. – С. 34. 3. Турецкий В. Я. Математика и информатика / В.Я. Турецкий. – 3-е изд., испр.… 4. Математика для гуманитариев: конспект лекций / Авт. – сост.: И.И. Клебанов, А. В. Дудин, Е. В. Коробейникова. –…