Сборник задач по дискретной математике (стр. 2 )

.

Пусть - множество логических функций. Формулой над F называется выражение вида , где , - либо переменная, либо формула. При этом множество F называется базисом, функция f называется главной (внешней) операцией, а - подформулами. Зная таблицу истинности базиса можно составить таблицу истинности функции, которую реализует (задает) данная формула.

Система функций {&,} образует булев базис, при этом формулы, содержащие только символы конъюнкции, дизъюнкции и отрицания, называются булевыми. Множество логических функций с заданным на нем булевым базисом образуют булеву алгебру.

Основные равносильности в булевой алгебре

(далее вместо записи будем писать или )

1.  , ;

2.  , ;

3.  , ;

4.  , ;

5.  ;

6.  , , , , ; ;

7.  , ;

8.  ;

9.  .

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

10. ;

11. ;

12. ;

13. ;

14. .

Под упрощением формул понимается получение формул, содержащих меньшее число символов. При упрощении используются равносильности:

15. поглощение: , ;

16. склеивание/расщепление: ;

17. обобщенное склеивание: .

Элементарными конъюнкциями (дизъюнкциями) называются конъюнкции (дизъюнкции) переменных или их отрицаний, в которых каждая переменная встречается не более одного раза. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций. Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ, каждая конъюнкция которой содержит все переменные или их отрицания. Конъюнктивная нормальная форма (КНФ) и совершенная конъюнктивная нормальная форма (СКНФ) определяются аналогично.

Функция называется двойственной к функции , если .

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

Множество логических функций с заданным на нем базисом {&,} образует алгебру Жегалкина. В алгебре Жегалкина выполнены все равносильности булевой алгебры, касающиеся конъюнкции, а также следующие равносильности:

18. ;

19. ;

20. ;

21. .

Логическая функция над базисом Жегалкина единственным образом представима полиномом Жегалкина:

.

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

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

22. ;

23. .

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

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

Классами Поста являются следующие замкнутые классы логических функций:

·  класс функций, сохраняющих 0: ;

·  класс функций, сохраняющих 1: ;

·  класс самодвойственных функций: ;

·  класс монотонных функций: ;

·  класс линейных функций: , где .

Логические функции можно интерпретировать как функции проводимости электрических цепей, содержащих двухпозиционные переключатели (частный случай так называемые релейно –контактные схемы). 1 интерпретируется как состояние переключателя “ ток проходит ”, а 0 – “ ток не проходит ”. x – замыкающий контакт, - размыкающий контакт, &- последовательное соединение контактов, - параллельное. Две цепи считаются эквивалентными, если через одну из них ток проходит тогда и только тогда, когда он проходит через другую. Из двух схем более простой считается та, которая содержит меньшее число контактов.

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

а) если на улице идет дождь, то нужно взять с собой зонт или отменить прогулку;

б) если в - прямой и стороны и равны, то .

2.  Пусть А= “X любит Y”, В= “Y любит X”. Выразить следующие формулы на обычном языке:

а) ; б) ; в) ; г) ; д) ;

е) ; ж) ; з) ; и) ; к) .

3.  Установить истинность высказывания: «если Алексей знаком с Борисом и Борис знаком с Викой, то либо Алексей знаком с Викой, либо Алексей не знаком с Викой».

4.  На вопрос: «Кто из трех студентов изучал дискретную математику?» Получен верный ответ: «Если изучал первый, то изучал и третий, но неверно, что если изучал второй, то изучал и третий». Кто изучал дискретную математику?

5.  Определите, кто из четырех студентов сдал экзамен, если известно:
если первый сдал, то и второй сдал;
если второй сдал, то третий сдал или первый не сдал;
если четвертый не сдал, то первый сдал, а третий не сдал;
если четвертый сдал, то и первый сдал.

6.  Вычислить значение функции на наборах и .

а) ; б) ;

в) .

7.  Построить таблицы истинности следующих функций:

а) ;

б) ;

в) ;

г) ;

д) ;

е) .

8.  Выяснить какие из следующих формул являются тождественно истинными или тождественно ложными:

а) ;

б) ;

в)

г) ;

д) .

9.  Найти СКНФ и СДНФ функций (), заданных таблицей истинности:

10.  Найти СДНФ функции с помощью равносильных преобразований:

а) ; б) ; в) ;

г) ; д) ; е) .

11.  Найти СКНФ функции с помощью равносильных преобразований:

а) ; б) ; в).

12.  Указать СДНФ, выражающие следующие функции:

а) ровно две переменные ложны;

б) большинство переменных равно 1;

в) .

13.  Найти все существенные переменные функции:

а) ; б) ;

в) .

14.  Найти ДНФ функции , двойственной к данной:

а) ; б) .

15.  Применить принцип двойственности к следующим равносильностям:

а) ; б) ; в) .

16.  Найти многочлен Жегалкина для функции:

а) ; б) ;

в) ; г) .

17.  Дана функция проводимости релейно-контактной схемы . Построить схему.

а) ; б) .

18.  Найти минимальную ДНФ и построить р.-к. схему для функции:

а) ; б) .

19.  Дана р.-к. схема. Записать функцию проводимости и упростить схему:

а) x б) y z

x y

x z

z

в) x

x

y x

y

z

z

u

u

20.  Из контактов x, y, z составить схему так, чтобы она имела состояние 1, если не менее двух контактов имеют состояние 1.

21.  Проверить полноту систем функций:

а) ; б) ; в) ; г) ; д) ; е) .

22.  Проверить принадлежность функций классам Поста:

а) ; б) ;

в) ; г) .

Глава III. Логика высказываний.

Функции алгебры логики

Высказыванием называется повествовательное утверждение, которое либо истинно, либо ложно (но не то и другое одновременно). Высказывание называется простым (элементарным), если оно рассматривается как одно неделимое целое. Простые высказывания обозначаются переменными, принимающими истинностные значения И и Л. Сложное высказывание - высказывание, составленное из простых с помощью логических связок. Логические связки (операции) будем интерпретировать как функции, заданные на множестве {И, Л} («истина», «ложь»} со значением в этом же множестве.

Функцией алгебры логики (или логической функцией) f от n переменных называется функция типа , где В={0,1}.

Любую логическую функцию можно задать таблицей истинности:

Значения переменных	Значение функции

Следующая таблица задает логические функции двух переменных:

		обозначение	наименование
			константа 0
			конъюнкция
			переменная
			переменная
			неравнозначность
			дизъюнкция
			стрелка Пирса
			эквивалентность
			отрицание
			импликация
			отрицание
			импликация
			штрих Шеффера
		1	константа 1

Логическая функция существенно зависит от переменной , если существует такой набор значений , что