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 нужно заменить:

Из принципа двойственности вытекает, что

.

В частности,

.


 

А также другие работы, которые могут Вас заинтересовать

23731. Признаки и свойства делимости 59.5 KB
  С какой целью мы их изучали Чтобы быстрее определять делится ли число сумма произведение на заданное число. а Найдите числа 365 Чтобы найти часть от числа надо число разделить на знаменатель и умножить на числитель получится 292; б Найдите число если его равны 146. Чтобы найти результат надо число разделить на числитель и умножить на знаменатель получится 219 2. а любое число не делящееся на 10; Что бы сумма делилась на число надо чтобы каждое слагаемое делилось на число: 140 делится на 10 значит x должен делиться на...
23732. Простые и составные числа 46.5 KB
  Образовательные: познакомить учащихся с понятием простого и составного числа повторить понятие делителя и классификации закрепить алгоритм решения задач на движение. 1 Прежде всего вспомним какое число называется делителем числа а Делителем числа a называется число на которое а делится без остатка или: b делит а если существует такое число с что а = bс. Запишите делители числа 30.
23733. Логическое кодирование 137.5 KB
  Основаны на разбиении исходной последовательности бит на порции, которые называют символами. Затем каждый исходный символ заменяется на новый, который имеет большее количество бит, чем исходный.
23734. Амплитудно-частотная характеристика, полоса пропускания, затухание и пропускная способность 176 KB
  Волоконно-оптический кабель также искажает передаваемый сигнал, что обусловлено различным временем распространения мод и наличием частотной зависимости показателя преломления материала оптического кабеля.
23735. Простые и составные числа 45 KB
  Формировать способность к рефлексивному анализу собственной деятельности: к фиксированию собственных затруднений по теме «Простые и составные числа», выявлению их причин и построению проекта выхода из затруднений...
23736. Алгоритмы разложения чисел на простые множители 40 KB
  Тренировать способность к практическому использованию алгоритма разложения чисел на простые множители; повторить и закрепить признаки делимости действия со смешанными числами решение задач на проценты составление геометрических фигур из частей.
23737. Разложение чисел на простые множители 44.5 KB
  Основная цель: сформировать способность представления числа в виде произведения простых множителей; повторить и закрепить: понятие простого и составного числа признаки делимости. Из получившегося ряда чисел назовите числа кратные 3. Из получившегося ряда чисел назовите числа кратные 9. Из получившегося ряда чисел назовите числа кратные 6.
23738. Язык и логика 84.5 KB
  2 а Подставим вместо переменных x и y их значения и найдём значение получившегося числового выражения по действиям. Если x = 15 y = 6 то 49  15 17  6 = 633 49  15 = 735; 17  6 = 102; 735 102 = 633 Сравним получившийся результат с число стоящим в правой части данного равенства. 633 = 533 Л б Подставим вместо переменных x и y их значения и найдём значение получившегося числового выражения по действиям. Подставим результат в исходное предложение вместо левой части 15 ≤ 3 Л 3 Надо найти такое число в разряде единиц...
23739. ОСТРЫЕ УГЛЫ МОЛОДЫХ СЕМЕЙ ИЛИ ШПАРГАЛКА ДЛЯ МОЛОДОЖЕНОВ 3.83 MB
  Книга Андрея Зберовского написана в традиционной для автора форме, где большая часть практических советов подана в увлекательной и живой форме, нередко с элементами юмора. Она адресована очень широкой читательской аудитории любых возрастных категорий, прежде всего – молодоженам!