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

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

.

В частности,

.


 

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

69126. Поняття алгоритму й основні алгоритмічні структури. Властивості та способи опису алгоритму. Алгоритмічна структура розгалуження і перетворення 56.5 KB
  Одним з базових понять інформатики є поняття алгоритму. Алгоритм вказує, які операції, пов’язані з обробкою даних, і в якій послідовності треба виконати, щоб отримати розв’язок задачі. Алгоритм розрахований на певного виконавця, з погляду котрого вказівки мають бути елементарними...
69127. Робота у середовищі Borland Pascal 7.0 202.5 KB
  Інтегроване середовище розробки Borland Pascal 7.0 - далі IDE (Integrated Development Environment) Borland Pascal 7.0 - складається з текстового редактора, компілятора, компонувальника, налагоджувача і довідкової системи. Стандартна поставка IDE Borland Pascal 7.0 являє собою...
69128. Словник мови та загальна структура програми. Алфавіт та словник мови 58 KB
  У будь-якій мові програмування програма — це набір зрозумілих компілятору команд. Для створення програм треба знати синтаксис мови, тобто правила запису команд і використання лексичних одиниць мови. Знайомство з мовою розпочнемо з алфавіту.
69129. Прості типи даних. Операції над даними 93 KB
  Поняття типу даних є одним із фундаментальних понять програмування. Тип даних визначає: множину допустимих значень яких може набувати змінна або константа зазначеного типу; множину допустимих операцій що застосовуються до даних певного типу; спосіб зображення даних...
69130. Константи, змінні, вирази. Найпростіші оператори. Процедури введення, виведення 126.5 KB
  Будь-які значення, що використовуються у програмі, - це або значення змінних, або константи. Принципова відмінність між змінними і константами полягає у тому, що для зберігання значень змінних під час виконання програми відводяться ділянки...
69131. Алгоритмічний вибір альтернатив. Вкладеність конструкцій вибору 48 KB
  Під час програмування деяких розгалужень виникає потреба у використанні операторних блоків що розглядатимуться у розділі 3. У цьому ж розділі буде пояснено як орієнтуватися в коді великих програм що містять численну кількість конструкцій вибору та операторних блоків.
69132. Алгоритмічна конструкція повторення. Цикл з передумовою, постумовою, лічильником. Переривання циклу 83.5 KB
  У заголовку циклу зазначається умова завершення циклу а тіло циклу являє собою блок операторів що повторюються. Кожне виконання операторів тіла циклу супроводжується перевіркою умови завершення циклу і називається його ітерацією.
69133. Підпрограми, їх різновиди та способи використання. Процедури та функції користувача. Стандартні процедури та функції 83.5 KB
  Одним із найпростіших і найважливіших застосувань циклічних структур є генерування рекурентних послідовностей. Ефективність розв’язання деяких математичних задач цілком залежить від вибору рекурентної послідовності та способу її обчислення. До таких задач належать, зокрема...
69134. Полевые транзисторы. Их основные параметры и характеристики 44.5 KB
  Различают три основных разновидности транзисторов: Полевой транзистор с управляемым pnпереходом: з затвор с сток и исток Входная характеристика: Выходная характеристика: МДП-транзисторы металл диэлектрик полупроводник транзисторы с встроенным каналом:...