1. Элементы математической логики и алгебра Буля

Логические функции

	x: 0 1 0 1	Условное обозначение	Название
	y: 0 0 1 1
f0	0 0 0 0	“0”	Константа 0
f1	0 0 0 1	; “”; ()	Конъюнкция (И)
f2	0 0 1 0	; xy;	Запрет Х
f3	0 0 1 1	y	Переменная "Y"
f4	0 1 0 0	; xy;	Запрет Y
f5	0 1 0 1	x	Переменная X
f6	0 1 1 0	x  y	Исключающее ИЛИ
f7	0 1 1 1	“”; +	Дизъюнкция (ИЛИ)
f8	1 0 0 0	;	Стрелка Пирса (ИЛИ-НЕ)
f9	1 0 0 1	;	Равнозначность
f10	1 0 1 0		Инверсия X
f11	1 0 1 1	;	Импликация от X к Y
f12	1 1 0 0		Инверсия Y
f13	1 1 0 1	;	Импликация от Y к X
f14	1 1 1 0	x|y ;	Штрих Шеффера (И-НЕ)
f15	1 1 1 1	“1”	Константа 1

Аксиомы и теоремы булевой алгебры

1. Свойства операций И/ИЛИ/НЕ

; ; ; ; ; .

2. ; (закон идемпотентности).

3. ; .

4. (закон двойного отрицания).

5. ; (перестановочный закон).

6. ; (закон поглощения).

7. ; .

8. ; (закон склеивания).

9. ; (теорема Де Моргана).

10. (сочетательный закон).

11. (ассоциативный закон).

12. ; (дистрибутивный закон).

Задачи

1. Запишите таблицы истинности для следующих формул:

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) ;

з) ;

и)

к)

2. Проверьте с помощью таблиц истинности следующие тождества:

а) ;

б) ;

в) ;

г)

д)

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

а) ;

б) ;

в) .

4. Запишите формулы для следующих высказываний, обозначив буквами входящие в них простые высказывания:

а) Давление падает и система не работает;

б) Вычисления выполнены точно или конструкция несовершенна;

в) Проект разработал Андрей или Петр, а эксперимент выполнил Иван;

г) Если будет хорошая погода, мы отправимся на стадион или пойдем за грибами;

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

е) Если я поеду на автобусе, то опоздаю на работу, или я воспользуюсь такси;

ж) Андрей помогает Петру или Петр помогает Андрею, или они помогают друг другу;

з) Не верно, что идет дождь и очень жарко;

и) Если телевизор не сломан и подключен к сети питания, я увижу «Новости».

к) Если есть лодка и работа выполнена, то начальство отпустит на рыбалку.

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

а)

б)

6. Пусть высказывания A означает: “число 2 - четное”, высказывание B - “число 3 - четное”, высказывание C - “число 4 - четное”. С помощью высказываний A, B, C и знаков логических операций построить формулы, содержанием которой является следующее высказывание

а) числа 2 и 3 четные;

б) число 3 – четное или число 4 – нечетное;

в) если число 2 - четное, то число 3 – нечетное;

г) четность числа 2 равносильна четности числа 4;

д) если числа 2 и 3 - четные, то число 4 одновременно и четное и нечетное;

е) хотя бы одно из чисел 2, 3, 4 – четное;

ж) ни одно из чисел 2, 3, 4 не является четным;

з) ровно два числа из набора чисел 2, 3, 4 - четные

и) не все числа 2, 3, 4 - нечетные;

к) по крайней мере два числа изнабора чисел 2, 3, 4 – четные.