Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Булева алгебра высказываний (алгебра логики)Содержание книги Поиск на нашем сайте
Высказыванием об элементах множества U называется любое утверждение об элементах множества U, которое для каждого элемента либо истинно, либо ложно. U = {1 2 3 4 5 6 7 8 9}
A = «число четное» B = «число, меньшее пяти»
Множеством истинности высказывания называется совокупность всех элементов, для которых это высказывание истинно.
SA = {2 4 6 8} SB = {1 2 3 4}
Высказывание, для которого множество истинности пусто, называется тождественно ложным, а для которого SB = U называется тождественно истинным. Высказывания, для которых множества истинности совпадают, называются тождественными или равносильными. Равносильные высказывания объединим в один класс Р.В. и не будем их разделять, т.к. все они имеют одно и то же множество истинности.
Операции над высказываниями Дизъюнкция высказываний (V, ИЛИ, OR) Дизъюнкция высказываний – высказывание, истинное тогда, когда истинно хотя бы одно из высказываний. Конъюнкция высказываний (&, И, AND). Конъюнкцией высказываний называется высказывание, истинное тогда и только тогда, когда истинны все высказывания. Отрицание высказываний (- над буквой, НЕ, NOT). Отрицанием высказывания называется высказывание, истинное только тогда, когда исходное высказывание ложно.
Л – ложно. И – истинно.
Утверждение (основа всей алгебры логики) Между множеством всех классов эквивалентных высказываний об элементах множества U и множеством P(U) можно установить взаимно однозначное соответствие, при котором операция дизъюнкции высказываний соответствует операции объединения множеств истинности, а конъюнкция соответствует операции пересечения. Операция отрицания соответствует операции дополнения. Следствие. Множество классов эквивалентных высказываний является булевой алгеброй. Теорема Существуют 3 булевых алгебры: 1. P(U) 2. Bn 3. Множество классов эквивалентных высказываний. Три булевых алгебры являются изоморфными, если между их элементами можно установить такое однозначное соответствие, при котором операции сохраняются.
Договоримся конъюнкцию обозначать точкой (как знак умножения в алгебре чисел). Конъюнкция выполняется раньше дизъюнкции (аналог выполнения операций сложения и умножения в алгебре чисел). Лекция 3 Определение и способ задания булевых функций
Булевой функцией от n аргументов называется однозначное отображение n – мерного булева куба на одномерный булев куб.
Способы задания функций 1. Табличный
gi - значение функции от данных аргументов. Порядок возрастания векторов по мере возрастания их номеров называют лексикографическим. 2. Векторный F = (g1...gn) 3. Геометрический Единичным вектором для данной функции называется тот вектор, значение функции на котором равно 1. Носителем данной функции – совокупность всех единичных векторов этой функции (Nf – носитель функции f)
На векторах, помеченных звездочкой, функция обращается в 1.
Nf = {001, 011, 100, 110} = [1,3,4,6] [] – указаны номера векторов.
3. В виде формулы. Функция f зависит от переменной xi фиктивно, если для любых двух наборов значений переменных, отличающихся только значением переменной xi, значения функции f совпадают. Будем говорить, что f зависит от переменной xi существенно, если существуют такие два набора значений, отличающихся только значением переменной xi, на которых значения функций различно. Фиктивные переменные у функции можно добавлять и исключать. Две булевы функции называются равными или равносильными, если одну можно получить из другой путем добавления и изъятия фиктивных переменных.
Строим таблицу функций при n = 1.
Таблица всех элементарных булевых функций, применяемых в записи формул
Все эти функции от двух аргументов мы и будем называть элементарными булевыми функциями. Основными элементарными функциями являются конъюнкция, дизъюнкция и отрицание. Элементарные булевы функции удовлетворяют всем аксиомам булевой алгебры. Суперпозиции булевых функций Ф = {ф1…фk}
F называется элементарной суперпозицией функции из множества Ф, если она получена одним из следующих способов. 1. Переименование какого-нибудь аргумента в одной из функций системы (возможно отождествление аргумента). 2. В одну из функций системы вместо любого аргумента ставится значение любой функции из этой системы.
Ф1 = {Y…xn} Фi = (x1 … фj(x1…xn) … xn)
Ф(1) – множество всех элементарных суперпозиций из системы Ф. Ф(k+1) – множество всех элементарных суперпозиций из систему Фk.
Функция g называется суперпозицией функций из системы, если $ N: g Î Фn Это означает, что g можно получить из функции системы Ф, применяя конечное число раз операцию элементарной суперпозиции. Конкретное выражение суперпозиции будем называть формулой над системой Ф. G = Fф Суперпозиция элементарных булевых функций – формула. Для удобства записи договоримся, что отрицание – самая сильная операция. Следующая – конъюнкция, а остальные – равносильны. _ _ X+Y = XY V XY _ _ X ~ Y = XY V XY __ X ® Y = X V Y _ _ X ¯ Y = X Y Лекция 4
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-04-18; просмотров: 327; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.116.90.57 (0.008 с.) |