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

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

.

В частности,

.


 

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

49096. Схема смешанной системы связи и сигналы в различных ее сечениях 1.59 MB
  Рассчитать: априорные вероятности и передачи нуля и единицы по двоичному ДКС; ширину спектра сигнала ИКМ. Рассчитать и построить спектр сигнала дискретной модуляции и определить ширину его спектра. Рассчитать: приходящуюся в среднем на один двоичный символ бит мощность и амплитуду сигнала дискретной модуляции необходимую для обеспечения требуемого ОСШ ; пропускную способность гауссовского НКС. Построить функции плотности вероятности ФПВ мгновенных значений и огибающей узкополосной гауссовской помехи УГП а также...
49098. Структурная схема смешанной системы связи и сигналы в различных её сечениях 2.85 MB
  Рассчитаем энергетическую ширину спектра Δf: Δf= Максимальное значение спектральной плотности мощности: Gmx=G0=4924104; Подставив это значение в формулу для расчета ширины спектра и посчитав интеграл получаем значение: Δf=3250 [Гц]. Рассчитаем интервал корреляции τ: τ=dτ=7692 [мкс].3 Рассчитаем мощность Рх отклика ФНЧ: Рх==2346 [В2]. Рассчитаем СКП фильтрации...
49099. Региональные особенности продуктивного пласта АС11 в Фроловской нефтегазоносной области 10.98 MB
  В результате работы будут даны обобщенные выводы, каким образом и почему, продуктивность пласта, даже при близком региональном расположение может быть разной. Будут сделаны заключения, как различные характеристики влияют на породы коллекторы...
49100. МАКРОЭКОНОМИЧЕСКАЯ ДИНАМИКА РЫНОЧНОГО ХОЗЯЙСТВА 452 KB
  Процентная ставка – один из самых важных механизмов, с помощью которого осуществляется регуляция экономики страны. В частности, вопросы темпов экономического роста и инфляционное давление регулируются именно с помощью ставки процента
49101. Принцип построения систем электросвязи и расчёта их параметров 2.43 MB
  Затем сигнал Xt дискретизируется во времени в дискретизаторе далее квантуется по уровню и затем квантованные уровни кодируются. Для передачи полученного ИКМсигнала необходимо использовать один из видов дискретной модуляции в нашем случае ДОФМ. В передающем устройстве ПДУ системы на основе аналогоцифрового преобразования АЦП сообщение преобразуется в первичный цифровой сигнал импульснокодовой модуляции ИКМ в результате при использовании ДОФМ формируется канальный сигнал St. При передаче сигнала по узкополосному непрерывному...
49102. Анализ помехоустойчивости и эффективности системы передачи информации 525 KB
  В приемном устройстве ПРУ системы принятая смесь сигнала и шума подвергается некогерентной НП обработке с последующим поэлементным принятием решения методом однократного отсчета. Рассчитать: априорные вероятности и передачи нуля и единицы по двоичному ДКС; ширину спектра сигнала ИКМ. Рассчитать и построить спектр сигнала дискретной модуляции и определить ширину его спектра . Рассчитать: приходящуюся в среднем на один двоичный символ бит мощность и амплитуду сигнала дискретной модуляции необходимую для обеспечения...
49103. Реализация алгоритмов решения задач при проектировании САУ с использованием объектно-ориентированного языка программирования C++ 810 KB
  Найти минимальное значение целевой функции. Недостатком является требование задания целевой функции в аналитическом виде унимодальности целевой функции в заданном интервале изменения переменной дифференцируемости целевой функции. Найти значения целевой функции в пробных точках . Определить минимальное значение целевой функции путем сравнения значений функции в пробных точках Метод равномерного поиска требует выполнения большого числа вычислений.
49104. Проектирование информационных систем 723.5 KB
  Информация об управляющей компании Цель компании ЛОИС помочь предприятиям в повышении эффективности бизнеса и качества предоставляемых услуг за счёт применения информационных систем разработанных компанией. Информация об управляющей компании Управляющая компания оказывает услуги доверительного управления клиентам. Компания совершает операции с собственными активами и также предоставляет оперативную отчётность о состоянии собственных активов компании акционерам и руководству компании.