67605
Булева алгебра, математическая логика, алгебра логики
Лекция
Математика и математический анализ
Каждому двоичному набору можно сопоставить число номер опр расстоянием Хемминга между вершинами и куба называется число опр наборы и называются соседними если и противоположными если все координаты разные.
Русский
2014-09-12
273 KB
1 чел.
Лекция №14 (14.03.00)
Булева алгебра, математическая логика, алгебра логики.
Литература:
1. Яблонский. Введение в дискретную математику. 1986, Москва, “Наука”
2. Гаврилов, Сапоженко. Задачи и упражнения по курсу дискретной математики.
опр || набор =(1, 2,…, n) где i{0,1}, i=1,…,n называется Булевым (двоичным) набором.
- i - компоненты набора (координаты вектора)
- n длина набора (размерность).
опр || нормой вектора называют сумму его координат.
опр || множество всех двоичных наборов длины n образуют n-мерный булев (или двоичный) куб . Наборы называют вершинами куба .
Каждому двоичному набору можно сопоставить число (номер)
опр || расстоянием Хемминга между вершинами и куба называется число
опр || наборы и называются соседними если и противоположными если (все координаты разные).
опр || набор предшествует (или не больше) набора (), если i i, i=1,…,n.
Если , , то набор строго меньше (строго предшествует) набору ().
опр || наборы и называются сравнимыми, если или .
опр || набор непосредственно предшествует если и
утв || отношение является отношением частичного порядка на множестве .
опр || функция определенная на множестве и принимающая значения из множества {0,1} называется функцией алгебры логики (булевой функцией).
Множество всех булевых функций, зависящих от будем обозначать .
При n = 0 функция называется ноль местной (const) f=0 или f=1.
В произвольном случае f можно задать таблицей
… |
f |
||||
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
0 |
||
0 |
0 |
0 |
1 |
1 |
|
… |
… |
… |
… |
… |
… |
1 |
1 |
1 |
… |
1 |
1 |
в которой наборы выписываются в порядке возрастания их номеров.
Имея в виду такое расположение наборов функцию можно задать вектором ее значений
(1, 2,…, k), k=2n.
Элементарные функции
0 и 1 - местные
x |
f=0 |
f=1 |
f1 |
f2 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
f=0 - тождественный ноль,
f=1 - тождественная единица,
f1(x)=x тождественная функция
;; - отрицание x, не x, not x
Двуместные функции
f3 |
f4 |
f5 |
f6 |
f7 |
f8 |
f9 |
f10 |
f11 |
||
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
f3 - называется конъюнкция
f4 - дизъюнкция
f5 - сложение по модулю 2
f6 - эквиваленция (когда )
f7 - импликация
из правды правда, из лжи правда/ложь
f8 - штрих Шеффера, (антиконъюнкция, не-и)
f9 стрелка Пирса, антидизъюнкция, функция Вебба, не или
Символы … называются логическими связками.
опр || зависит существенным образом от аргумента , если такие значения переменных , что .
опр || Если для всех наборов то переменная xi называется фиктивной переменной.
опр || функции f1 и f2 называются равными, если f1 получается из f2 добавлением или изъятием фиктивных элементов.
Формулы
опр ||Формулой над множеством Ф функциональных символов будем называть всякое (и только такое) выражение вида
1) 0, 1- константы;
2) x-любая переменная из множества X;
3) выражения вида (UB), где U,B формулы, - символ любой двуместной связки (,,,,,).
4) - отрицание;
Для сокращения записи формул принимаются следующие соглашения:
а) внешние скобки опускаются;
б) считается, что операция отрицания выполняется в первую очередь;
в) следующей по старшинству считается операция конъюнкции; затем все остальные.
Примеры:
- не есть формула, так как неправильно стоят скобки,
- не стоят скобки вообще
Сопоставим формуле функцию
опр || Функцию называют симметричной по переменным , если для подстановки
Основные эквивалентности алгебры логики
Свойства:
1) коммутативность
2) ассоциативность
3) дистрибутивность
а)
б)
в)
4) правила Деморгана
а)
б)
5) правила поглощения
а)
б)
6)
а)
б)
7
а)
б)
в)
г)
д)
8)
а)
б)
в)
9)
а)
б)
Примеры
Доказать эквивалентность формул
Двойственные функции
опр || функция называется двойственной функцией к функции .
Пример.
x1 |
x2 |
x3 |
||
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
Правило ||
Чтобы получить двойственную функцию нужно инвертировать , а затем перевернуть таблицу.
Соответствие элементарных функций
f 0, 1, x, , x1&, x1
f* 1, 0, x, , x1, x1&
Из определения двойственности следует, что
Теорема || Пусть
Тогда
Доказательство ||
Отсюда вытекает принцип двойственности: двойственной к формуле
является формула .
Пусть формула содержит только символы &, , . Тогда для получения из U нужно заменить:
Из принципа двойственности вытекает, что
.
В частности,
.
А также другие работы, которые могут Вас заинтересовать | |||
5577. | Изучение свойств, форм и операций мышления | 44 KB | |
Изучение свойств, форм и операций мышления Цель работы:исследование: свойства мышления: лабильности (подвижности) форм мышления: структура и соотношение понятий операций мышления: сравнение, обобщение, абстрагирование. Матери... | |||
5578. | Исследование эффективности различных видов организационных структур | 177 KB | |
Структура организации - это основной элемент любой организации, не только характеризующий её, но и представляющий собой сам механизм построения и функционирования организации. Правильный выбор организационной структуры - необходимый фактор ... | |||
5579. | КРОВЬ КАК ВНУТРЕННЯЯ СРЕДА ОРГАНИЗМА И СРЕДСТВО ТРАНСПОРТА ВЕЩЕСТВ. ФИЗИКО-ХИМИЧЕСКИЕ СВОЙСТВА КРОВИ | 177.94 KB | |
Функциональная система крови (состав, функции, методы исследования). Физико-химический состав гомеостаз внутренней среды (состав и физико-химические показатели крови). Кровь как средство транспорта веществ. | |||
5580. | Подшипники качения | 113.5 KB | |
Отличие подшипников качения от подшипников скольжения. В любом механизме или машине различают два типа подвижных опор: опоры с трением скольжения и опоры с трением качения. В первом случае происходит взаимное перемещение и взаимодействие рабочих пов... | |||
5581. | Изучение свойств памяти | 55 KB | |
Изучение свойств памяти Цель работы:исследование динамики процессов запоминания выявление преобладающего вида образной памяти (зрительная, слуховая). Материалы:Методики для исследования памяти: Динамический тест памяти Таблицы с образам... | |||
5582. | Обоснование и расчет искусственного освещения помещения здания закусочной | 98 KB | |
Обоснование и расчет искусственного освещения помещения здания закусочной Задание 1. Требования руководящих документов по вопросам производственной санитарии и гигиены труда 2. Анализ опасных и вредных факторов при строительстве и эксплуатации здани... | |||
5583. | Уголовная статистика и изучение преступности | 93.5 KB | |
Правовая статистика охватывает широкий круг проблем, связанных с негативными явлениями в обществе. Изучает различного рода преступления и правонарушения, такие как: бандитизм, ограбление, изнасилование, проституция... | |||
5584. | Материалы и изделия, получаемые спеканием и плавлением. Керамика | 207 KB | |
Материалы и изделия, получаемые спеканием и плавлением 1. Керамические материалы. Общие сведения Керамика - собирательное название широкой группы искусственных каменных материалов, получаемых формованием из глиняных смесей с минеральными и ... | |||
5585. | Магнитное поле в вакууме | 30 KB | |
Магнитное поле в вакууме: Взаимодействие токов осуществляется через поле, называемое магнитным. Из опытов следует, что оно имеет направленный характер и должно характеризоваться векторной величиной, называемой магнитной индукцией (В), аналогич... | |||