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

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

.

В частности,

.


 

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

25864. мажорных обстоятельств. 24 KB
  Под риском понимается угроза потери части своих ресурсов недополучение доходов или произведение дополнительных расходов в результате проведения финансовых операций.Внутренние риски: Риск ликвидности; Процентный риск; Кредитный риск; Валютный риск Внешние риски: Рыночный риск; Политический риск; Риск изменения конъюнктуры рынка; Страновой риск; Риск форсмажорных обстоятельств. Процентный риск связан с колебаниями процентных ставок на рынке.
25865. Характеристика методов финансового анализа деятельности банков 24.5 KB
  Роль финансового анализа в управлении деятельностью коммерческих банков повышение надежности и качества управления. Объектами финансового анализа в банке прежде всего могут быть показатели финансовых результатов результативности и финансового состояния в банке; показатели эффективности системы финансового управления; эффективности банковских услуг операций и т. К методам финансового анализа деятельности банка относят: структурный анализ отчетности позволяющий определить удельные веса относительные показатели; метод группировки...
25867. Экономическая сущность ликвидности баланса коммерческого банка 26.5 KB
  Различают следующие понятия ликвидности: рынка достаточное количество денежных средств у участников рынка для обеспечения его нормального функционирования; банка способность своевременно погашать свои обязательства; баланса соответствие соотношения отдельных статей баланса установленным нормативам; активов скорость и наличие возможностей трансформации их отдельных видов в денежные средства.Ликвидность банкапредполагает уде ежеднев.устойчивость банка.
25868. Анализ выполнения экономических нормативов деятельности КБ 22.5 KB
  Для обеспечения устойчивости банковской системы Центральный банк РФ устанавливает ряд экономических нормативов т. Посредством экономических нормативов регулируется вопервых абсолютный и относительный уровень собственного капитала кредитной организации вовторых ликвидность баланса; втретьих диверсификация активных и пассивных операций кредитной организации; вчетвертых создание каждой кредитной организацией централизованных резервов для обеспечения финансовой устойчивости банковской системы в целом. Для соблюдения указанных...
25869. Анализ движения и структуры кредитов, выданных банком 21 KB
  Содержание анализа кредх операций: крты группся по срокам объемам по видам клиентов анализся состав клиентов сроки сопостовлся с предыдущим годом. Далее опредся объем ссудных операций в общей сумме операций норматив 08 если меньше то ситуация отрицная.
25870. Анализ динамики дебиторской и кредиторской задолженности банка по видам и срокам возникновения 23 KB
  Дебиторской задолженности традиционно рассматривается в двух аспектах: в соответствии со сроками ее погашения: 1.краткосрочная платежи по которой ожидаются в течение 12 месяцев после отчетной даты; в соответствии с причинами возникновения задолженности : 1. Анализ кредиторской задолженности начинается с оценки структуры и динамики источников заемных средств: 1.