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

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

.

В частности,

.


 

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

45470. Информационно-измерительные системы и АСУТП 238 KB
  Помехи в системах связи ИВС. Помехи в системах связи ИВС Материал из Пермский Студенческий Портал. Перейти к: навигация поиск Помехи в системах связи ИВС.3 По соотношению ширины спектра сигнала и помехи 1.
45471. ОПРЕДЕЛЕНИЕ И ЗАДАЧИ ИНФОРМАЦИОННОЙ ТЕХНОЛОГИИ 47 KB
  Для любой технологии могут быть выделены цель предмет и средства. Целью технологии в промышленном производстве является повышение качества продукции сокращение сроков ее изготовления и снижение себестоимости. Методология любой технологии включает в себя: декомпозицию производственного процесса на отдельные взаимосвязанные и подчиненные составляющие стадии этапы фазы операции; реализацию определенной последовательности выполнения операций фаз этапов и стадий производственного процесса в соответствии с целью технологии;...
45472. ТРАНСПОРТИРОВАНИЕ ИНФОРМАЦИИ 75.5 KB
  При разработке и использовании сетей для обеспечения совместимости используется ряд стандартов объединенных в семиуровневую модель открытых систем принятую во всем мире и определяющую правила взаимодействия компонентов сети на данном уровне протокол уровня и правила взаимодействия компонентов различных уровней межуровневый интерфейс Международные стандарты в области сетевого информационного обмена нашли отражение в эталонной семиуровневой модели известной как модель OSI Open System Intercongtction связь открытых систем...
45473. ОБРАБОТКА ИНФОРМАЦИИ 62 KB
  Широкая альтернатива принимаемых решений приводит к необходимости использования разнообразных математических моделей Создание документов сводок отчетов заключается в преобразовании информации в формы пригодные для чтения как человеком так и компьютером. Принятие решений в условиях определенности. Поэтому между выбранной стратегией использования ресурсов и конечным результатом существует однозначная связь откуда следует что в условиях определенности достаточно использовать решающее правило для оценки полезности вариантов решений...
45474. ХРАНЕНИЕ ИНФОРМАЦИИ 1.07 MB
  В настоящее время определяющим направлением реализации этой операции является концепция базы данных склада хранилища данных. База данных может быть определена как совокупность взаимосвязанных данных используемых несколькими пользователями и хранящихся с регулируемой избыточностью. Банк данных система представляющая определенные услуги по хранению и поиску данных определенной группе пользователей по определенной тематике. Система баз данных совокупность управляющей системы прикладного программного обеспечения базы данных...
45475. ПРЕДСТАВЛЕНИЕ И ИСПОЛЬЗОВАНИЕ ИНФОРМАЦИИ 52.5 KB
  Важным признаком который необходимо учитывать при разработке и внедрении информационных технологий является отношение человека к информации. Основной задачей операции представления информации пользователю является создание эффективного интерфейса в системе человек компьютер. При этом осуществляется преобразование информации в форму удобную для восприятия пользователя.
45476. Базовые информационные технологии МУЛЬТИМЕДИА-ТЕХНОЛОГИИ 30 KB
  Достигнутый технологический базис основан на использовании нового стандарта оптического носителя DVD Digitl Verslite Video Disk Использование DVD позволило реализовать концепцию однородности цифровой информации. Для решения этой проблемы используются методы компрессии звуковой информации. Такие значительные объемы при реализации аудио и видеорядов определяют высокие требования к носителю информации видеопамяти и скорости передачи информации.
45477. ГЕОИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ 27 KB
  Таким образом геоинформационные технологии предназначены для широкого внедрения в практику методов и средств работы с пространственновременными данными представляемыми в виде системы электронных карт и предметноориентированных сред обработки разнородной информации для различных категорий пользователей. Основные области использования ГИС: электронные карты; городское хозяйство; государственный земельный кадастр; экология; дистанционное зондирование; экономика; специальные системы военного назначения.
45478. Технология защиты информации 430.5 KB
  Выделяют следующие основные группы причин сбоев и отказов в работе компьютерных систем: нарушения физической и логической целостности хранящихся в оперативной и внешней памяти структур данных возникающие по причине старения или преждевременного износа их носителей; нарушения возникающие в работе аппаратных средств изза их старения или преждевременного износа; нарушения физической и логической целостности хранящихся в оперативной и внешней памяти структур данных возникающие по причине некорректного использования компьютерных...