Методические рекомендации по изучению дисциплины (стр. 2 )

 – ;

 – ;

 – .

Таким образом, ; ; |– С. Отсюда, применяя правило , получаем:

  ; |– .

Упражнение 1.

Доказать остальные производные правила вывода.

Пример 2.

Пусть А;В;С – произвольные формулы исчисления высказываний. С использованием производных правил вывода докажем, что:

а)  |–;

б)  |– ;

в)  |– ;

г)  |– ;

д)  |– ;

е)  |– ;

ж)  |– ;

з)  |– ;

и)  |–  ;

к)  |– ;

л)  |– ;

м)  |– ;

н)  |–  ;

о)  |– .

Действительно, соответствующие выводы имеют вид:

а) 1. |– – ;

2. |– – ;

3. |– –  (1);

4. |– –  (2);

5. |– – ;

6. |– – ;

7. |– –  (3;5);

8. |– –  (4;6);

9. |– –  (7;8);

10. |– –  (9);

11. |–  – ;

12. |–  –  (10;11).

В этом доказательстве и далее запись (2), к примеру, означает, что к утверждению |–, записанному под номером 2 применено правило контрапозиции , что и привело к утверждению |–. Аналогичным образом трактуются и записи типа (3;5); и т. д.

б) 1. |– – ;

2. |– – ;

3. |– –  (1);

4. |– –  (2);

5. |– –  (3;4).

д) 1. |– – М. Р.

2. |– – ;

3. |– –  (1;2);

4. |– – ;

5. |– –  (4);

6. |– –  (3);

7. |– –  (5);

8. |– –  (6;7);

9. |–;

10. |–  –  (8;9);

11.  – (10).

и) 1.  – ;

2.  – ;

3.  – ;

4.   – ;

5.  – (3;2);

6.  – (4;2);

7.  – (1;5);

8.  – (7;6).

о) 1.  – ;

2.  – ;

3.  – (1;2);

4.  – ;

5.  – (3;4);

6.  – ;

7.  – ;

8.  – (6;7);

9.  – ;

10.  – (8;9);

11.  – (5;10).

Упражнение 2.

Построить выводы соответствующие условиям оставшихся пунктов примера 2.

№ 4 Алгебра высказываний и нормальные формы.

№ 5 Функции алгебры логики и проблема построения минимальных Д. Н.Ф.

1.Булевы функции.

1.1 Двоичные наборы.

Двоичным набором длины п называется упорядоченная последовательность длины n, каждая координата которой принадлежит двухэлементному множеству ; . Множество всех двоичных наборов обозначается через (-я декартова степень множества Е).

Пример 1.1.1 .

Для краткости двоичный набор будем обозначать через и слово «двоичный» опускать.

Упражнение 1.1.1 Доказать, что число всех наборов длины n равно .

На множестве определяется бинарное отношение по правилу:

,

для любых и из .

Пример 1.1.2 Пусть ; и . Тогда , а наборы и не сравнимы относительно .

Упражнение 1.1.2 Доказать, что - частично упорядоченное множество.

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

-номеров называется стандартным.

Пример 1.1.3 Номером набора будет число .

Пример 1.1.4 Расположение

наборов длины 3 является стандартным.

Упражнение 1.1.3 Найти номера наборов:

а) ;

б) .

Упражнение 1.1.4 Расположить наборы из в стандартном порядке.

Упражнение 1.1.5 Доказать, что набор является записью числа в двоичной системе счисления.

Пример 1.1.5 Найдём двоичный набор длины 7, - номером которого является число 43.

Для нахождения набора, т. е. двоичного разложения числа 43, получаем равенства:

;

;

;

; (1)

;

;

,

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

.

Заметим, что цепочку равенств (1) можно продолжить и дальше:

…………...

т. е. число 43 будет также номером набора длины 8 и номером набора длины 9 и т. д.

Пусть . Положим:

Наборы и называются противоположными.

Упражнение 1.1.6 Найти двоичные наборы длины 9, - номерами которых являются числа: а) 198; б) 231.

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

Булевой функцией (или функцией алгебры логики) называется отображение f из в , число называется местностью или арностью функции f.

Если набору отображение f ставит в соответствие элемент , то используется запись или . Таким образом, булева функция f – это n – местная функция , аргументы которой принимают свои значения в множестве Е и значения самой функции ( на любом наборе значений для аргументов) также принадлежит множеству Е. Так как число наборов длины n конечно и равно (упражнение 1.1.1), то для задания n – местной булевой функции достаточно указать значений этой функции, которые она принимает на наборах из . Т. е. булеву функцию от n аргументов можно задать таблицей вида:

		……….
0	0	……….	0
0	0	……….	1
…	…	……….	…	……….
		……….
…	…	……….	…	……….
		……….	1

Таблица 1

Наборы в таблице 1 (сверху – вниз) в порядке возрастания - номеров.

Пример 1.2.1 Табличное задание функции , которая принимает значение 1 тогда и только тогда, когда большинство переменных принимает значение 0, имеет вид:

0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	0

Таблица 2