Следовательно, Сократ – смертен.

Этот силлогизм является частным случаем «первой фигуры» силлогизма:

Все, кто обладает свойством P, обладает свойством Q.

y обладает свойством P.                                                   .

Следовательно, y обладает свойством Q.

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

Предикатная запись первой фигуры силлогизма выглядит так:

                                  (5)

                                         (6)

                                            (7)

Формальный вывод заключения (7) из посылок (5) и (6) состоит в следующем:

1. В первую предикатную аксиому (1) вместо  подставим (импликация: если …, то …). Получим:

.               (8)

2. Из формул (8) и (5) по правилу Modus Ponens ( ) следует, что выводима формула

.                                        (9)

3. Из формул (9) и (6) по правилу Modus Ponens выводима формула , что и требовалось:

.

    Префиксной нормальной формой называется выражение вида:

,

где кванторы, навешанные на переменные  – предикатная формула, имеющая вид ДНФ.

УПРАЖНЕНИЯ

1. Предикат  задан на множестве N². Причем : «х > y»; :«х < y»; :«х  y»; : «х  y»; : «х делится на y без остатка»; «х и y имеют общий делитель, отличный от единицы».

При каких  будут истинны значения предиката :

1) х = 2 и у = 4;                       3) х = 5 и у = 5;

2) х = 4 и у = 2;                  4) х = 7 и у = 3;

предикатного выражения:

5) ;                7) ;

6) ;                8) .

2. Указать значения выражений, которые получаются при навешивании кванторов на переменные предиката:

1) P(x, y): « x<y», заданный на множестве натуральных чисел.

2) P(x, y): «x делится на y», заданный на множестве натуральных чисел.

3) P(x, y): «x и y одновременно четные числа», заданный на множестве натуральных чисел.

4) P(x, y): «x является родителем y», заданный на множестве людей.

5) P(x, y): «x является братом y», заданный на множестве людей.

6) P(x, y): «x живет в одной квартире с y», заданный на множестве людей.

7) P(x, y): «x и y лежат на одинаковом расстоянии от начала координат», заданный на множестве точек декартовой плоскости.

8) P(x, y): «x и y лежат на одинаковом расстоянии от оси ОХ», заданный на множестве точек декартовой плоскости.

3. Пусть на множестве М=  предикат P(x, y) задан таблицей.

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

4. Проверить тождественную истинность следующих предикатных формул:

1) ;

2) ;

3) ;

4) .

5. Получить префиксную нормальную форму следующих предикатных формул:

1) ;

2) ;

3) .

ГЛАВА 6. СХЕМЫ ПЕРЕКЛЮЧАТЕЛЕЙ.

КОМБИНАЦИОННЫЕ СХЕМЫ

Схемы переключателей

Релейно-контактные схемы (или переключательные схемы) широко используются в технике автоматического управления.

Под переключательной схемой понимают схематическое изображение некоторого устройства, состоящее из следующих элементов:

1) переключателей (ключей);

2) соединяющих их проводников;

3) входов в схему и выходов из нее (полюсов).

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

Переключателю  ставится в соответствие истинное высказывание: «переключатель Р разомкнут» или «переключатель  замкнут».

Таким образом, когда Р замкнут,  – разомкнут и наоборот.

Если высказывание Р истинно, то переключатель Р замкнут – схема пропускает ток, если ложно – не пропускает. Следовательно, любому высказыванию может быть поставлена в соответствие переключательная схема с двумя полюсами (двухполюсная схема).

Конъюнкции высказываний А и В соответствует последовательное соединение переключателей А и В:

Дизъюнкции высказываний А и В соответствует параллельное соединение переключателей А и В:

Так как любая формула логики высказываний может быть записана в виде ДНФ или КНФ, то ясно, что любой формуле можно сопоставить схему переключателей. Причем, упрощение формулы ведет к упрощению схемы.

Пример.

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

Итак, переключателей должно быть два. Пусть, например, свет не горит, и оба переключателя разомкнуты. Тогда, переключатель А замыкается, свет горит. Коридор пройден, переключатель В замыкается, свет не горит. Оба переключателя замкнуты – свет не горит. И наоборот.

Составим таблицу истинности.

Построим СДНФ данной логической функции.

.

Соответствующая схема переключателей имеет вид:

Комбинационные схемы

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

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

Наиболее важные типы комбинационных элементов приведены в таблице 1.

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

Таблица 1

Элементы	Конъюнкция	Дизъюнкция	Отрицание
Обозначения

Такие цепи называются комбинационными схемами (логическими сетями).

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

Пример.

Построить комбинационную схему в базисе «штрих Шеффера», реализующую дизъюнкцию .

Так как . А отрицание , то  дизъюнкция

.

Обозначим комбинационный элемент, соответствующий функции «штрих Шеффера» обозначим в виде:

    Тогда соответствующая схема приобретает вид:

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

УПРАЖНЕНИЯ

1. Центральная система теплоснабжения небольшого дома контролируется термостатами, каждый из которых расположен в одной из комнат. Каждый термостат срабатывает, если температура меньше 15 градусов Цельсия. В целях экономии центральный нагреватель включается только в том случае, если, по меньшей мере, в двух комнатах температура меньше 15 градусов. В противном случае, центральный нагреватель отключен. Изобразить схему переключателей, управляющую системой теплоснабжения.

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

3. Записать булеву формулу, соответствующую схеме переключателей, приведенной на рисунке.

Упростить выражение. Построить схему переключателей, соответствующую упрощенному выражению.

4. Упростить схемы переключателей.

Рис.1

Рис.2

5. Построить схему переключателей для следующих формул логики высказываний:

1) ;

2) ;

3) ;

4) ;

5) .

Упростить формулы, построить упрощенные схемы. Сравнить количество переключателей, необходимых для построения первоначальной и упрощенной схемы.

6. Записать формулу логической функции, соответствующую приведенной схеме из функциональных элементов. Упростить формулу. Построить схему, соответствующую упрощенной формуле.

Рис.1

Рис.2

 6. Построить схему из функциональных элементов И, ИЛИ, НЕ, соответствующую функции, заданной своей булевой формулой.

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) ;

8) .

7. Выразить логическую функцию через функцию «штрих Шеффера», затем через функцию «стрелка Пирса» и построить схему их функциональных элементов.

1) ;         4) ;

2) ;           5) ;

3) ;           6) .

Литература

1. Виленкин, Н. Я. Комбинаторика. – М.: Наука, 1969. – 328 с.

2. Гаврилов, Г. П. Задачи и упражнения по курсу дискретной математики: учеб. пособие / Г. П. Гаврилов, А. А. Сапоженко. – М.: Наука, 1992. – 408 с.

3. Гмурман, В. Е. Руководство к решению задач по теории вероятностей и математической статистике. – М.: Высшая школа, 1979.– 400 с., ил.

4. Гмурман, В. Е. Теория вероятностей и математическая статистика: учеб. для вузов. – 12-е изд., перераб. – М.: Высшее образование, 2008. – 479 с.: граф., табл.

5. Гутова, С. Г. Теория вероятностей и математическая статистика: учеб.-метод. пособие/ ГОУ ВПО «Кемеровский государственный университет»; сост. С. Г. Гутова. – Кемерово: ИНТ, 2008. – 108 с.

6. Кузнецов, О. П. Дискретная математика для инженера/ О. П. Кузнецов, Г. М. Адельсон-Вельский. – М.: Энергоатомиздат, 1986. – 480 с.

7. Кук, Д. Компьютерная математика: пер. с англ./ Д. Кук, Г. Бейз. – М.: Наука, Гл. ред. физ.-мат. лит., 1990. – 384 с.

8. Чуешева, О. А. Математическая логика: учеб.-метод. пособие/ сост. О. А. Чуешева. – Кемерово, 2006. – 48 с.

9. Щекочихина, С. Г. Дискретная математика: вопросы для самостоятельного изучения для студентов 1 курса МФ спец. 01.02. – Кемерово: Кузбассвузиздат, 2003. – 64 с.

10. Яблонский, С. В. Введение в дискретную математику: учеб. пособие. – М.: Наука, 1986. – 384 с.

ГУТОВА Светлана Геннадьевна

НЕВЗОРОВА Татьяна Анатольевна

ДИСКРЕТНАЯ МАТЕМАТИКА

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

по дисциплине «Дискретная математика»

Подписано к печати       . Формат 60×84 1/16. Печать офсетная. Бумага офсетная.

Печ. л. 8,0. Тираж 100 экз. Заказ №

ФГБОУ ВПО «Кемеровский государственный университет».

650043, Кемерово, ул. Красная, 6.

Отпечатано в издательстве.