Спецглавы

10

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

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

2.2.4. Дизъюнкция сильная (строгая) – сложное высказывание, которое образуется из простых с помощью союзов ™либо…, либо…®. Обозначается p q , читается ™либо p, либо q®. Сильная дизъюнкция двух высказываний о некоторых событиях обозначает, что происходит либо одно событие, либо другое, но не оба сразу. Члены строгой дизъюнкции, называемые альтернативами, не могут быть одновременно истинными.

Пример 12.

Рассмотрим высказывание: ™Либо я сдам экзамен по математике, либо меня отчислят®. Оно состоит из двух простых высказываний:

р: ™Я сдам экзамен®, р 1; q: ™Меня отчислят®, q 1.

Возможны следующие случаи.

1) Оба простых высказывания истинны ( р 1, q 1): ™Я сдам экзамен, меня отчислят®.

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

2) Одно высказывание истинно, втрое ложно, имеем: ™Я сдам экзамен, меня не отчислят® ( р 1 и q 0 ), или ™Я не сдам экзамен, меня отчислят® ( р 0 и q 1). Эти высказывания являются истинными, p q 1

3) Оба простых высказывания ложные ( р 0 и q 0 ). Сложное высказывание ™Я не сдам экзамен, меня не

отчислят® – ложное, p q 0

11

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

Сильная дизъюнкция будет истинна при истинности одного и ложности другого члена; она будет ложна, если оба члена истинны или оба ложны.

2.2.5. Импликация – сложное высказывание, которое образуется из простых с помощью союза ®если, то¯. Обозначается р q , здесь высказывание р – это посылка (условие), а высказывание q – заключение (следствие). Читается: ™Если р, то q®.

Пример 13.

™Если через проводник проходит электрический ток, то проводник нагревается®. Обозначим:

р: ™Через проводник проходит электрический ток®, р 1; q: ™Проводник нагревается®, q 1.

Рассмотрим ситуации:

1)™Если через проводник действительно проходит

Сложное высказывание является истинным, то есть р q 1.

2)™Если через проводник действительно проходит

3) ™Если через проводник не проходит электрический ток, то проводник нагревается® ( р 0 , q 1). Это высказывание считается истинным, потому что проводник может нагреваться и по другим причинам, р q 1.

4) ™Если через проводник не проходит электрический ток, то

13

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

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

Названия логических операций и образующие их союзы занесены в общую таблицу истинности (Табл.1).

2.3. Формализация сложных высказываний

Производится по следующему алгоритму.

1)Определяются простые высказывания, из которых состоит исходное высказывание. Простые высказывания обозначаются буквами: p, q,…A, B, C, … X, Y. Они называются логическими переменными.

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

15

две переменные истинны, одна – ложна ( два значения =1, одно=0); одна переменная истинна, две – ложные (одно значение =1, два=0), три переменные ложные ( все значения = 0).

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

Заполняем последний столбец по значениям 3-го и 4-го столбца. Конъюнкция является истинной тогда, когда оба исходных высказывания истинны, в остальных случаях она ложна (см. табл.1).

Анализируем полученную таблицу истинности. Исходное высказывание истинно (=1)в двух случаях:

™Поеду на автобусе ( А 1), не поеду на троллейбусе ( В 0 ), и буду слушать музыку в дороге (С 1)® или ™Не поеду на автобусе ( А 0 ), поеду на троллейбусе ( В 1), и буду слушать музыку в дороге (С 1)®.

Пример 16.

³Если мы вовремя закончим занятия и не пойдем гулять, то вернемся домой часа в четыре®.

Выделим простые суждения скобками: ³Если (мы вовремя закончим занятия) и не (пойдем гулять), то (вернемся домой часа в четыре)®.

Определим простые суждения:

А – ™ мы вовремя закончим занятия®; В – ™пойдем гулять®; С – ™вернемся домой часа в четыре®.

Суждение В входит в формулу с отрицанием (союз ™не®). Высказывания А и не-В соединены конъюнкцией (союз ™и®). Союз ™если, то® обозначает импликацию. Окончательная формула:

А В С .

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

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

Встолбце 5 – конъюнкция столбца 1 и 4, она истинна, когда оба значения истинны. В столбце 5 ставим значение 1 в тех строках, где и в столбце 1, и в столбце 4 стоит 1. В остальных строках ставим 0.

16

В столбце 6 – импликация, причем посылка в столбце 5, а следствие – в столбце 3. Импликация ложна только в одном случае, когда посылка истинна, а следствие ложно: 1 0 0. Смотрим, в каких строчках столбца 5 стоит 1, и в столбце 3 стоит 0. Имеем только одну строку, там проставляем 0, в остальных ставим 1.

Анализируем полученную таблицу истинности. Суждение ложно только в одном случае:

™Мы вовремя закончили занятия ( А 1), не пошли гулять ( В 0 ), и не вернулись домой часа в четыре (С 0)®.

2.4. Нахождение значений простых высказываний, входящих в сложное

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

1)Определяются простые высказывания.

2)Записываются формулы имеющихся сложных высказываний.

3)Если есть отрицание, то оно снимается. При этом значение

суждения изменяется на противоположное. Если А 0, то А 1. Если А 1, то А 0 .

Для определения значений простых высказываний используются исключительные, ™единственные® ситуации:

для конъюнкции: 1 1 1; для дизъюнкции: 0 0 0 ;

17

для импликации: 1 0 0.

ЗАДАНИЕ 3.

Считая, что каждое из данных сложных высказываний истинное, определите значения входящих в них простых высказываний. Рассмотрим пример.

Пример 17.

Даны три истинных высказываний о четырех подозреваемых: а) Если Абрамов виновен, то Сидоров тоже виновен; б) Неверно, что если Васильев виновен, то и Дубов тоже виновен; в) Неверно, что Сидоров виновен, а Дубов нет. Определите, кто из подозреваемых виновен.

1)Введём простые высказывания: А – ™Виновен Абрамов®, В

–™Виновен Васильев®, С – ™Виновен Сидоров®, Д – ™Виновен Дубов®.

2)Запишем формулы имеющихся сложных высказываний:

а) А С 1 б) В Д 1;

в )С Д 1.

3) Снимем отрицание со второго высказывания я В Д 1. Получим: В Д 0 . Импликация ложна (= 0) только в одном случае, когда 1 0 0. Отсюда имеем, что В 1, Д 0.

Подставим это значение в полученную формулу, имеем: С 1 0 .

Следовательно, высказывание В – ™Виновен Васильев® – истинно.

18

2.5. Логическая равносильность

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

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

ЗАДАНИЕ 4.

Установите, являются ли равносильными следующие суждения.

Пример 18.

Неверно, что если Иванов занимается боксом, то он не умеет плавать. Иванов занимается боксом и умеет плавать.

Выделим простые суждения:

p – ™Иванов занимается боксом®, q – ™Иванов умеет плавать®.

Первое высказывание обозначим А, и оно имеет формулу:

А p q . Второе высказывание обозначим В, его формула: В p q . Составим общую таблицу истинности для этих формул.

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

19

3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

3.1. Основные понятия

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

При изображении графов ребра могут быть прямолинейными или криволинейными; длины ребер и расположение вершин произвольны. На рис. 1.1 один и тот же граф изображен двумя способами.

V4

Рис. 3.1. Различное изображение одного графа

Приведем ряд примеров приложений теории графов.

1.™Транспортные® задачи, в которых вершинами графа являются пункты, а ребра – дороги (автомобильные, железные и др.) или другие транспортные (например, авиационные) маршруты. Другой пример – сети снабжения (энергоснабжения, газоснабжения, снабжения товарами и т. д.), в которых вершинами являются пункты производства и потребления, а ребрами – возможные маршруты перемещения (линии электропередач, газопроводы, дороги и т. д.) Соответствующий класс задач оптимизации потоков грузов, размещения пунктов производства и потребления и т. д. иногда называется задачами обеспечения или задачами о размещении. Их подклассом являются задачи о грузоперевозках.

2.™Технологические задачи®, в которых вершины отражают производственные элементы (заводы, цеха, станки и т. д.), а дуги – потоки сырья, материалов и продукции между ними, заключаются в