ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 04.08.2024
Просмотров: 1775
Скачиваний: 0
СОДЕРЖАНИЕ
1.4. Декартово произведение множеств
1.5.1. Определение бинарного отношения
1.5.2. Способы задания бинарного отношения
1.5.3. Свойства бинарных отношений
1.5.4. Отношения эквивалентности
1.7. Контрольные вопросы и упражнения
2.1.1. Логические высказывания
2.1.2. Основные логические операции
2.2.1. Булевы функции и операции
2.2.2. Совершенные дизъюнктивная и конъюнктивная нормальные формы
2.3. Полные системы логических функций
Класс функций, сохраняющих ноль
Класс функций, сохраняющих единицу
Класс самодвойственных функций
2.4.3. Минимизация днф методом Квайна
2.6. Контрольные вопросы и упражнения
3.1.2. Ориентированные и неориентированные графы
3.1.4. Частичные графы и подграфы
3.1.6. Изоморфизм. Плоские графы
3.2. Отношения на множествах и графы
3.3. Матрицы смежности и инциденций графа
3.5.1. Степени неориентированных графов
3.5.2. Степени ориентированных графов
3.6.1. Характеристики расстояний в графах
3.6.2. Характеристические числа графов
3.7.2 . Базисные циклы и разрезающие множества
Свойства базисных циклов и разрежающих множеств
3.7.3. Цикломатическая матрица и матрица разрезов
Составление цикломатической матрицы
3.8. Задача определения путей в графах
3.8.1. Определение путей в графе
3.8.2. Алгоритм определения кратчайших путей
Все множество наборов переменных по значениям функции на них можно разбить на 2 подмножества:
[1] – единичное множество наборов, на которых f = 1;
[0] – нулевое множество наборов, на которых f = 0.
Теперь определим количество различных функций nпеременных. Каждая функция задается набором своихkзначений, которому также можно поставить в соответствиеk-разрядное двоичное число.
Располагая функции
в таблице в порядке возрастания
соответствующих им чисел, мы получим
все возможные различные функции.
Количество таких функций будет равно
.
Далее рассмотрим логические функции одной и двух переменных, которые определяют также и операции, используемые при записи логических формул. Их можно считать «элементарными» функциями (табл. 2.4, 2.5).
Таблица 2.4. Функции g(x)
|
х |
g1(x) |
g2(x) |
g3(x) |
g4(x) |
|
0 1 |
0 0 |
0 1 |
1 0 |
1 1 |
Таблица 2.5. Функции двух переменных f(х1, х2)
|
х1 х2 |
f1 |
f2 |
f3 |
f4 |
f5 |
f6 |
f7 |
f8 |
f9 |
f10 |
f11 |
f12 |
f13 |
f14 |
f15 |
f16 |
|
0 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
1 1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
Функции одной переменной
Функция g2(х) =x определяет логическую операцию –повторениепеременнойx, а функция g3(х) =x определяет логическую операцию –отрицаниепеременнойx.
g1(х) иg4(х) по сути являются не функциями, а константами 0 и 1.
Функции двух переменных
f2= х1 х2 – конъюнкция или логическое умножение
f8= х1x2 – дизъюнкция или логическое сложение.
f10 = х1 х2 – эквивалентность;
f7= х1х2– неэквивалентность;
f12= х2х1– функция следования (импликации) х1;
f14= х1х2 – функция следования (импликации) х2;
f3= х1х2 – функция запрета х1;
f5= х2х1 – функции запрета х2;
f9= х1x2– функция (стрелка) Пирса;
f15= х1| х2 – функция (штрих) Шеффера.
Причем, функции f2, f8, f10, f12, f14 определены ранее как основные логические функции (табл. 2.1).
Функции f3, f5, f7, f9, f15 являются производными от них:
f
f
f
f
f
Остальные 6 функций, по сути, не являются функциями от двух переменных. Функции f4,f6,f11,f13 зависят существенно только от одной переменной:
f4(х1, х2) = х1, f6(х1, х2) = x2,
f11(х1, х2) =х2, f13(х1, х2) =х1.
Функции f1,f16 не зависят ни от одной переменной и являются функциями – константами:
f1(х1, х2) = 0, f16(х1, х2) = 1.
Замечание. Операция неэквивалентности (х1х2), определяющая функциюf7(х1, х2), имеет и другие названия. В математической логике она известна еще как операция «исключающее или», а в двоичной алгебре – как операция «сложение по модулю два».
Исходя из рассмотренных элементарных функций, можно построить формулы для более сложных функций трех и более числа переменных.
Пример.ФормулаF= ((х1х2) •х2)х3 определяет функцию трех переменныхf(х1, х2, х3 ).
Таким образом, суперпозиция элементарных функций позволяет получить другие логические функции конечного или бесконечного числа переменных. Совокупность всех возможных логических функций образует множество, которое обозначим P2.
2.2. Булева алгебра
2.2.1. Булевы функции и операции
Существуют много видов алгебр логики, в которых произвольная логическая функция представляется как суперпозиция некоторых базисных функций. Например, широко известной является булева система функций: конъюнкция (), дизъюнкция () и отрицание ( ). Эта система функций в качестве базиса была введена английским математиком Булем, с именем которого связано начало всей математической логики. Поэтому алгебра логики на основе этих операций называется алгеброй Буля илибулевой алгеброй. Рассмотрим свойства булевых операций.
Свойства булевых операций
1. Аксиоматические свойства
х • х = х, x x = x,
x •x = 0, x x = 1, х • 0 = 0, x 0 = x,
x • 1 = x, x 1 = 1.
2. Свойства коммутативности
х1 х2 = х2 х1,
х1 • х2 = х2 • х1.
3. Свойства ассоциативности
(х1 х2) х3 = х1 (х2 х3),
(х1 • х2) • х3 = х1 • (х2 • х3).
4. Свойства дистрибутивности
(х1 х2) • х3 = (х1 • х3) (х2 • х3),
(х1 • х2) х3 = (х1 х3) • (х2 х3).
5. Принцип двойственности (Закон де Моргана)
х
х
1
х2
= х1
•х2.
6. Закон двойного отрицания: х =х.
В булевой алгебре любая логическая функция может быть представлена булевой формулой в виде совершенной дизъюнктивной формы (СДНФ). Причем, как будет показано ниже, представление произвольной логической функции в виде СДНФ является единственным.