Логические формулы. Решение логических задач.

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

A ®ВÚС;

(A « Ú ) ® Ù ;

B ® Ú (С Ù B) «(A Ú B) Ù ® С и т.д.

Такие высказывания называются логическими формулами, а входящие в них простые высказывания – логическими переменными. Символы Ø, Ù, Ú, ®, «называют логическими связками.

Принимая А, В, С за обозначение простых высказываний, логическая формула будет представляться как определенное сложное высказывание. Например, если обозначить А – «Будет дождь», В – «Я возьму зонт», С – «Я надену плащ», то A®ВÚС – запись сложного высказывания «Если будет дождь, то я возьму зонт или надену плащ».

Для правильного вычисления значения логических формул необходимо задать порядок выполнения логических операций. Сначала выполняется операция отрицания Ø, затем конъюнкция Ù и дизъюнкция Ú (они равноправны), затем импликация ® и, последней, эквивалентность «. Как и в алгебре, скобки необходимы для изменения порядка действий, а равноправные операции вычисляются слева направо.

Таким образом, для вычисления значения выражения

(A « Ú ) ® Ù

необходимо сначала определить и , затем выполнить дизъюнкцию Ú , после этого подсчитать значение выражения, стоящего в скобках: A« Ú , далее выполнить конъюнкцию высказываний Ù и, наконец, соединить вычисленные значения высказываний A « Ú и Ù с помощью импликации: (A « Ú ) ® Ù . Порядок выполнения операций будет таков:

.

Вычислим значение истинности этой логической формулы при всевозможных комбинациях значений логических переменных, составляющих эту формулу. Делать такие вычисления удобнее с помощью таблицы, в каждой строке которой анализируется одна комбинация значений простых высказываний, а в столбцах вычисляются все операции по порядку. Такие таблицы, построенные для сложных высказываний, называются таблицами истинности или таблицами Куайна^[2].

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

Пример 8. Построим таблицу истинности для приведенного выше сложного высказывания:

(A « Ú ) ® Ù .

Так как и А, и В могут принимать два значения, то различных комбинаций значений А и В будет четыре:

А=1, В=1;

А=1, В=0;

А=0, В=1;

А=0, В=0.

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

Пусть простые высказывания А и В истинны: А=1, В=1. Тогда и являются ложными высказываниями: =0, =0. Также ложной будет и дизъюнкция Ú =0. Значение высказывания в скобках A« Ú =0, так как эквивалентность истина«ложь дает ложь. Конъюнкция ложных высказываний Ù также ложна: Ù =0. Результирующее высказывание представляет собой соединение ложь®ложь, что по определению операции импликация есть истина. Значит, (A « Ú ) ® Ù =1 при А=1 и В=1.

А	В			Ú	A« Ú	Ù	(A « Ú ) ® Ù

Двойной чертой отделяем значения исходных переменных от вычисляемых значений по определениям логических операций.

Если логическая формула состоит из трех переменных А, В и С, то строк в таблице истинности будет 8. Действительно, для каждого значения высказывания С, а их два: истина и ложь, существуют 4 комбинации значений А и В.

Если в сложном высказывании – n простых, то логических возможностей – строк таблицы истинности будет . К примеру, при n=10, число различных комбинаций значений переменных - число строк таблицы .

Пример 9. В деле об убийстве имеются двое подозреваемых - Иванов и Петров. Допросили четырех свидетелей, которые последовательно дали такие показания: "Иванов не виноват", "Петров не виноват", "Из двух первых показаний по меньшей мере одно истинно", "Показания третьего ложны". Четвертый свидетель оказался прав. Кто виновен?

Решение:: Обозначим через I высказывание «Виноват Иванов», P — «Виноват Петров». Именно эти высказывания являются простыми, исходными. Тогда показания подозреваемых описываются следующими формулами алгебры высказываний:

Первый свидетель S₁: ØI.

Второй свидетель S₂: ØP.

Третий свидетель S₃: S₁ÚS₂=ØIÚØP.

Четвертый свидетель S₄: Ø S₃ = Ø(ØIÚØP).

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

 

Исходные высказывания	Утверждения
Первого свидетеля	Второго свидетеля	Третьего свидетеля	Четвертого свидетеля
I	P	ØI	ØP	ØIÚØP	Ø S3

Пример 10. Иванов, Петров и Сидоров подозреваются в совершении преступления. В ходе следствия они дали следующие показания:

Иванов: Петров виновен, а Сидоров нет.

Петров: Если Иванов виновен, то виновен и Сидоров. (Они всегда действуют сообща).

Сидоров: Я невиновен, но хотя бы один из них двоих виновен.

Необходимо установить:

а) Совместимы ли показания всех троих подозреваемых, т.е. могут ли они быть одновременно истинны?

б) Предполагая, что показания всех обвиняемых истинны, укажите, кто виновен, а кто нет?

в) Если все трое невиновны, то кто лжесвидетельствует?

Решение: Обозначим через I высказывание «Виноват Иванов», P — «Виноват Петров», S — «Виноват Сидоров». Именно эти высказывания являются простыми, исходными. Тогда показания подозреваемых описываются следующими формулами алгебры высказываний:

Иванов: P Ù .

Петров: I ® S.

Сидоров: Ù (I Ú P).

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

Исходные высказывания	Вспомогательные формулы	Утверждения	Пункты задачи
Иванова:	Петрова:	Сидорова:
I	P	S		I Ú P	P Ù	I ® S	Ù (I Ú P)
								а), б)
								в)

Теперь ответим на вопросы задачи.

а) Показания Иванова, Петрова и Сидорова одновременно истинны, т.е. имеют значение 1, в шестой строке таблицы. Таким образом, показания всех подозреваемых совместны.

б) Если показания всех обвиняемых истинны (пункт а) – шестая строка таблицы), то в этом случае P=1, а I=0 и S=0, т.е. виновен Петров, а Иванов и Сидоров – невиновны.

в) И, наконец, если все подозреваемые невиновны P=0, I=0, S=0 (восьмая строка), то лишь Петров говорит правду, а Иванов и Сидоров по какой-то причине лжесвидетельствуют.

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

Факт того, что В является логическим следствием высказываний записывается так: ½= В. Эта запись читается: «Пусть , тогда В» или «Из следует В».

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

Пример 11. Проверить следующее рассуждение: «Если гражданин законопослушен, он не совершит преступления. Гражданин Иванов - не законопослушен. Значит, он совершит преступление».

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

Рассмотрим строки, в которых высказывания и одновременно истинны. Таких строк две: третья и четвертая. В третьей строке высказывание В также истинно, а вот в четвертой – ложно. Таким образом, не во всех случаях, когда высказывания и одновременно истинны высказывание В будет также истинно. Высказывание В называют не является логическим следствием высказываний , . Вывод: рассмотренное рассуждение неверно.

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

 

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

1. Понятие высказывания.

2. Логические операции: отрицание, дизъюнкция, конъюнкция, импликация, эквивалентность.

3. Логические формулы. Решение логических задач.

Основная литература

1. Информационные технологии в юридической деятельности: учебник для бакалавров / под общ. ред. П.У. Кузнецова. – М: Издательство Юрайт, 2012. – 422с. – Серия: Бакалавр. ISBN 978-5-9916-1509-9.

2. Давыдов, А.С. Математика и информатика. Раздел «Математика»: учебное пособие / А.С. Давыдов, А.П. Соколов. – Челябинский юридический институт МВД РФ (ЧелЮИ МВД России), 2010. – 76 с.

3. Гресс, П.В. Математика для гуманитариев: учебное пособие / П.В. Гресс. – М.: Университетская книга, Логос, 2010. – 160 с. ISBN 978-5-98704-094-9.

4. Арбузов, П.В. Высшая математика для юристов: учебное пособие / П.В. Арбузов, В.Н. Герасименко, С.В. Гуде, Д.В. Медянцев. – Ростов-на-Дону: Феникс, 2009. – 448 с. – ISBN: 978-5-222-12688-2.

Дополнительная литература

5. Информатика. Базовый курс: учебное пособие: рекомендовано Министерством образования и науки РФ / под ред. С. В. Симонович. – СПб: Питер, 2009. – 639 с. ISBN 5-947237-52-8 (*).

6. Попов, А.М. Информатика и математика: учебное пособие: рекомендовано УМЦ / А.М. Попов, В.Н. Сотников, Е.И. Нагаева, под ред. А.М. Попова. – Москва: ЮНИТИ-ДАНА, 2008. – 302 с. ISBN 5-238-01396-1 (*).

7. Информационные технологии в юридической деятельности. Учебное пособие для бакалавров. Гриф МО РФ / под редакцией В.Д. Элькина. – М: Юрайт, 2012. – 527 c. ISBN 978-5-9916-1766-6.

[1] От английских слов «true» и «false».

[2] Уиллард Ван Орман Куайн (1908—2000) – американский философ, логик и математик.