рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

F5 – повторение по y

F5 – повторение по y - раздел Философия, Курс лекций По дисциплине ДИСКРЕТНАЯ МАТЕМАТИКА F6 – Сумма По Модулю 2 ...

f6 – сумма по модулю 2

f7 – дизъюнкция

f8 – стрелка Пирса

f9 – эквивалентность

f10 – отрицание y

f11 – импликация от y к x

f12 – отрицание x

f13 – импликация от x к y

f14 – штрих Шеффера

f15 - константа 1.

 

Для инженера ВТ алгебра логики (ВТ – алгебра переключательных схем или комбинационная логика) является системой алгебраических методов решения логических задач, а также совокупных задач, решаемых такими методами; для ВТ - это инструмент синтеза комбинационных схем, являющихся частным случаем конечных ????, элементной базой которого является либо функциональные элементы,

Предметом двузначной алгебры логики явл. однородные двузначные логические и операции над ними, а также вытекающие из их свойств правила преобразования

(упрощение, минимизация) с целью алгоритмизации решения задач.

В алгебре логики высказывания рассматриваются только с точки зрения истинности или ложности без рассматривания их смысла.

Индекс функции fi(x, y) является десятичным эквивалентом двоичного числа, образованного из вектора значений функции на упорядоченном множестве наборов значений аргументов: {(0,0),(0,1),(1,0),(1,1)}. Функции f0, f3, f5, f10, f12, f15 являются расширением на случай двух переменных уже известных функций одной переменной. Функции f1(x,y) = x ∨ y (конъюнкция) и f7(x,y) = x ∧ y (дизъюнкция) совместно с функцией инверсии (f10, f12) были использованы в предыдущих разделах для построения форм представления переключательных функций, пригодных для аналитической записи переключательных функций произвольной сложности.

Рассмотрим более подробно эти функции. Две из них f0 = 0 и f15 = 1 являются константами. Наиболее важные функции двух переменных имеют специальные названия и обозначения. Заметим, что эти обозначения не всегда общеприняты.

Перечислим 7 важнейших функций:

1) конъюнкция (функция И) двух высказываний X и Y называется высказывание XY, которое истинно только в том случае, когда X и Y оба истинны.

Таблица истинности для конъюнкций

X Y XY

Заметим, что конъюнкция – это фактически обычное умножение (нулей и единиц). Иногда эту функцию обозначают X&Y или XY.

 

2) дизъюнкция (функция ИЛИ) двух высказываний X и Y называется высказывание XY, которое истинно только в том случае, когда X и Y оба истинны.

Таблица истинности для дизъюнкций

X Y XY

 

3) импликация (следование) двух высказываний X и Y называется высказывание XY, которое истинно тогда и только тогда, когда X истинно, а Y ложно.

Таблица истинности для импликации

X Y XY

Иногда импликацию обозначают x→y (читается “из x следует y”).

Это очень важная функция, особенно в логике. Ее можно рассматривать следующим образом: если х = 0 (т.е. х “ложно”), то из этого факта можно вывести и “ложь”, и “истину” (и это будет правильно), если у = 1 (т. е. у “истинно”), то истина выводится и из “лжи” и из “истины”, и это тоже правильно. Только вывод “из истины ложь” является неверным. Заметим, что любая теорема всегда фактически содержит эту логическую функцию.

 

4) сложение по модулю 2 (здесь и далее, если не оговорено противное, знаком будем обозначать такое сложение) двух высказываний X и Y называется высказывание XY, которое истинно тогда и только тогда, когда X истинно, а Y ложно или X ложно, а Y истинно. Сумма по модулю два, или антиэквивалентность, по определению

Таблица истинности для импликации

X Y XY

5) эквивалентность или подобие двух высказываний X и Y называется высказывание XY, которое истинно тогда и только тогда, когда X и Y оба истинны или ложны.

Таблица истинности для эквивалентности

X Y XY

Эта f9 = 1 тогда и только тогда, когда х = у. Заметим, что будем применять оба обозначения: ху (в основном при изучении функций) и х ~ у (когда речь будет идти о логических операциях).

6) штрих Шеффера двух высказываний X и Y называется высказывание , которое ложно только, когда оба высказывания истины. По определению штрих Шеффера является антиконъюнкцией .

Таблица истинности для штриха Шеффера (антиконъюнкции)

X Y

Иногда эту функцию называют “не и” (так как она равна отрицанию конъюнкции).

Замечание. Конъюнкция, дизъюнкция, отрицание были определены для объектов, принимающих лишь два значения 0 и 1. Однако бывают случаи, когда можно ввести такие операции для некоторых других объектов (эти операции также называют иногда конъюнкцией, дизъюнкцией и отрицанием), для которых также выполнены свойства 1–6. В этом случае говорят, что на этих объектах введена булева алгебра.

7) стрелка Пирса (иногда эту функцию называют штрих Лукасевича) двух высказываний X и Y называется высказывание , которое истинно только, когда оба высказывания ложны. По определению стрелка Пирса (штрих Лукасевича) является антидизъюнкцией .

Таблица истинности для стрелки Пирса (антидизъюнкцией)

X Y

Эта функция является отрицанием дизъюнкции и поэтому иногда ее называют “не или”.

Заметим, что свойства последних двух функций (как будет видно далее) похожи между собой и, может быть, поэтому в литературе их часто путают (т. е. называют f8 штрихом Шеффера, а f14 – стрелкой Пирса).

Замечание. Во всех вышеприведенных таблицах истинности логических операций число строк 2n, где n – число простых высказываний.

Три оставшиеся функции, (f2 , f4 и f11) особого значения в дискретной математике не имеют.

Заметим, что часто будут рассматриваться функции от функций, т. е. суперпозиции перечисленных выше функций. При этом последовательность действий указывается (как обычно) скобками. Исключение составляет конъюнкция (которая на самом деле является обычным умножением в двоичной системе). Поэтому конъюнкция совершается первой, даже если отсутствуют скобки. Например, запись xyyz означает (xy) (yz).

Из перечисленных функций особую роль играют три функции, а именно конъюнкция, дизъюнкция и отрицание, поэтому рассмотрим более подробно их свойства.

Помимо этих связок используются еще три связки полученные из вышеуказанных связок

Название Прочтение Обозначение
Штрих Шеффера Антиконъюнкция
Стрелка Пирса Антидизъюнкция
Сумма по модулю два Антиэквивалентность

Штрих Шеффера или антиконъюнкция, по определению

Стрелка Пирса или антидизъюнкция, по определению

Сумма по модулю два или антиэквивалентность, по определению

Таблицы истинности этих операций

X Y Штрих Шеффера Стрелка Пирса Сумма по модулю 2

 

– Конец работы –

Эта тема принадлежит разделу:

Курс лекций По дисциплине ДИСКРЕТНАЯ МАТЕМАТИКА

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ... ИНСТИТУТ ЭКОНОМИКИ УПРАВЛЕНИЯ И ИНФОРМАЦИОННЫХ СИСТЕМ В СТРОИТЕЛЬСТВЕ... ИЭУИС...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: F5 – повторение по y

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Предмет дискретной математики
Предмет дискретная (финитная, конечная) математика – направление математики, изучающее свойства дискретных структур, в то время как классическая (непрерывная) математика изучает свойства объ

Изоморфизм
Наука, изучающая алгебраические операции называется алгеброй. Это понятие по мере изучения курса будет конкретизироваться и углубляться. Алгебру интересует только вопрос, КАК действуе

Упражнения
1. Докажите, что изоморфное отображение всегда изотонно, а обратное утверждение неверно. 2. Запишите на языке множеств свою группу. 3. Запишите на языке множеств предметы, которые

Множество и элементы множества
В настоящее время существующие теории множеств различаются парадигматикой (системой взглядов) концептуального базиса и логических средств. Так, в качестве примера, можем привести две противоположны

Конечные и бесконечные множества
То, из чего состоит множество, т.е. объекты, образующие множество, называется его элементами. Элементы множества различны и отличаются друг от друга. Как видно из приведенных пример

Мощность множества
Мощность для конечного множества равна числу его элементов. Например, мощность универсума В(A) множества A мощностью n

А1A2A3| + … + |А1A2A3| + … + |А1A2An| + … + |Аn-2An-1An| + (-1)n-1 |А1A2A3…An|.
Конечное множество А имеет мощность k, если оно равномощно отрезку 1.. k;:

Подмножество, собственное подмножество
После того как введено понятие множества, возникает задача конструирования новых множеств из уже имеющихся, то есть определить операции над множествами. Множество М',

Символический язык содержательных теорий множеств
В процессе изучения курса будем различать объектный язык теории множеств и метаязык, средствами которого изучается объектный язык. Под языком теории множеств будем понимать реляцион

Доказательство
Множество В бесконечно, значит,

Добавление и удаление элементов
Если А — множество, а х — элемент, причем , то элемент

Ограниченные множества. Границы множеств
Пусть на некотором множестве X задана числовая функция f(х). Верхней гранью (границей) функции f(х) называется такое число

Точная верхняя (нижняя) граница
Совокупность всех верхних границ Е обозначается через Еs, всех нижних границ - через Еi. В случа

Точная верхняя (нижняя) граница множества
Если элемент z принадлежит пересечению множества E и множеству всех его верхних границ Es (соответственно нижних г

Основные свойства верхних и нижних границ
Пусть X - частично упорядоченное множество. 1. Если , то

Множество с атрибутивной точки зрения
Агрегатная точка зрения, в отличие от атрибутивной, является логически несостоятельной в том плане, что она приводит к парадоксам типа Рассела и Кантора (см. ниже). В рамках атрибутивной т

Структура
Частично упорядоченное множество X называется структурой, если в нем любое двухэлементное множество

Покрытие и разбиение множеств
Разбиением множества А называется семейство Аi

Бинарные отношения
Последовательность длины п, члены которой суть а1, .... аn, будем обозначать через {а1, .... а

Свойства бинарных отношений
Бинарное отношение R на множестве Хобладает следующими свойствами: (а) рефлексивно, если хRх

Тернарные отношения
Декартовым произведением XY

N-арные отношения
По аналогии с декартовым произведением двух множеств X,Y можно построить декартово произведение X

Отображения
Отображения – это некоторые связи между элементами множеств. Простейшими примерами отношений являются отношения принадлежности х

Соответствие
ПодмножествоSдекартового произведения называетсяn-арным соответствиeмэлементов множествMi. Формально

Функция
В основе всех разделов дискретной математики лежит понятие функции. Пусть Х —

Представление функции в терминах отношений
Функцией называется бинарное отношение f, если из и

Инъекция, сюръекция, биекция
При использовании термина «отображение» различают отображение ХвY и отображение Х на Y

Обратная функция
Для произвольных , определим

Частично упорядоченные множества
Множество S называется частично упорядоченным (ЧУМ), если на нем задано рефлексивное, транзитивной и антисимметричное бинарное отношение частичного порядка

Минимизации представления множества
Используя эти законы, рассмотрим задачу минимизации представления множества М с помощью операций

Перестановки
Дано множество A. Пусть A – конечное множество, состоящее из n элементов A = {a1, a2, …, a

Перестановки с повторениями
Пусть в множестве A имеются одинаковые (повторяющиеся) элементы. Перестановкой с повторениями состава (n1, n2, … ,nk

Размещения
Кортежи длины k (1≤k≤n), состоящие из различных элементов n-элементного множества A (кортежи отличаются од

Размещения с повторениями
Пусть во множестве A имеются одинаковые (повторяющиеся) элементы. Размещениями с повторениями из n элементов по k назы

Упорядоченное размещение
Разместим п объектов по m ящикам так, чтобы каждый ящик содержал бы последовательность, а не множество, как прежде, помещенных в нем объектов. Два

Сочетания
Из m-элементного множества A построим упорядоченное множество длины n, элементы которого являются размещениями с одними и тем

Сочетания с повторениями
Полученные формулы справедливы только, когда в множестве A нет одинаковых элементов. Пусть имеются элементы n видов и из них составляется кортеж из

Метод производящий функций
Этот метод используется для перечисления комбинаторных чисел и установления комбинаторных тождеств. Исходным пунктом являются последовательность {ai} комбинатор

Алгебраическая система
Алгебраической системой A называется совокупность ‹M,O,R›, первая составляющая которой M есть непустое множество, вторая компонента O – множество

Замыкание и подалгебры
Подмножество называется замкнутым относительно операции φ, если

Алгебры с одной бинарной операцией
Пусть на множестве М задана одна бинарная операция. Рассмотрим порождаемые ею алгебры, но предварительно рассмотрим некоторые свойства бинарных операций. Бинарная о

Группоид
Алгебра вида <М, f2>называется группоидом. Если f2 — операция типа умножения (

Фактор-множества и фактор-алгебра
Если отношение R обладает свойствами: рефлексивное симметричное транзитивное, т.е. является отношением эквивалентности (~ или ≡ или Е) на множестве M

Целые числа по модулю m
Дано кольцо целых чисел <Z; +, >. Напомним. Алгебра <М,

Конгруэнции
Конгруэнцией на алгебре A = <A; Σ> (Σ – сигнатура алгебры состоит только из функциональных символов) называется такое отношение эквивалентности

ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
Графы - математические объекты. Теория графов применяется в таких областях, как физика, химия, теория связи, проектирование ЭВМ, электротехника, машиностроение, архитектура, исследование о

Граф, вершина, ребро
Под неориентированным графом (или короче графом) будем понимать такую произвольную пару G = <V, E>, что

Соответствие
Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, ко

Неориентированный граф
Если ребра не имеют ориентации, то граф называется неориентированным (неориентированный дубликат или неориен

Инцидентность, смешанный граф
Если ребро е имеет вид {и, v } или <и, v>, то будем говорить, что ребро е инцидентно вер

Обратное соответствие
Поскольку представляет собой множество таких вершин

Изоморфизм графов
Два графа G1 = <V1, E1> и G2 = <V2, E2> изоморфны (G

Путь, ориентированный маршрут
Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в котор

Смежные дуги, смежные вершины, степень вершины
Дуги а = (хi, хj), хi ≠ хj, имеющие общие концевые вершины, н

Связность
Две вершины в графе называются связным, если существует соединяющая их простая цепь. Граф называется связным, если все его вершины связны. Теорема.

Граф со взвешенными дугами
Граф G = (N, A) называется взвешенным, если на множестве дуг A определена некоторая функция l: A → R, которую на

Матрица сильной связности.
Матрица сильной связности: по диагонали ставим 1; заполняем строку X1 - если вершина достижима из X1 и X1 д

ДЕРЕВЬЯ
Деревья важны не только потому, что они находят приложения в различных областях знаний, но и Вилу особого положения их в самой теории графов. Последнее вызвано предельной простотой строения деревье

Следствие 1 В любом нетривиальном дереве имеются по крайней мере две висячие вершины.
Доказательство Рассмотрим дерево G(V, Е). Дерево — связный граф, следовательно,

Теорема
Центр свободного дерева состоит из одной вершины или из двух смежных вершин: Z(G) = 0&k(G) = 1 → С(G) = К1

Ориентированные, упорядоченные и бинарные деревья
Ориентированные (упорядоченные) деревья являются абстракцией иерархических отношений, которые очень часто встречаются как в практической жизни, так и в математике и программировании. Дерево (ориент

Доказательство
1. Каждая дуга входит в какой-то узел. Из п. 2 определения 9.2.1 имеем: v

Упорядоченные деревья
Множества Т1,.. ., Тk в эквивалентном определении ордерева являются поддеревьями. Если относительный порядок поддеревьев Т1,.. .,

Бинарные деревья
Бинарное (или двоичное) дерево - это конечное множество узлов, которое либо пусто, либо состоит из корня и двух непересекающихся бинарных деревьев - левого и правого. Бинарное дерево не яв

Представление свободных деревьев
Для представления деревьев можно использовать те же приёмы, что и для представления графов общего вида — матрицы смежности и инциденций, списки смежности и другие. Но используя особенные свойства д

End for
  Обоснование Код Прюфера действительно является представлением свободного дерева. Чтобы убедиться в этом, покажем, что если Т' — дерево

Представление бинарных деревьев
Всякое свободное дерево можно ориентировать, назначив один из узлов корнем. Всякое ордерево можно произвольно упорядочить. Для потомков одного узла (братьев) упорядоченного ордерева определено отно

Основные логические функции
Обозначим через E2 = {0, 1} – множество, состоящее из двух чисел. Числа 0 и 1 являются основными в дискретной мате

Булева функция.
Булевой функцией от n аргументов x1, x2, … ,xn, называется функция f из n-ой степени множества

Двухэлементная булева алгебра.
Рассмотрим множество Во = {0,1} и определим на нем операции , согласно таблицам ист

Таблицы булевых функций
Булева функция от n переменных может быть задана таблицей, состоящей из двух столбцов и 2n строк. В первом столбце перечисляются все наборы из B

Порядок выполнения операций
Если в сложном выражении скобок нет, то операции надо выполнять в следующем порядке: конъюнкция, дизъюнкция, импликация, эквивалентность, отрицание. Соглашения относительно расстановки ско

Эквивалентность формул
Различные формулы могут иметь одинаковые таблицы истинности. Так возникает понятие эквивалентности формул. Формулы φ(x1,..., xn) и

Замечание
1. Формула φ тождественно ложна тогда и только тогда, когда неφ тождественно истинна (|=неφ ); 2. Формула φ

Фактор-алгебра алгебры формул
Обозначим через Фn множество всех формул алгебры логики с переменными из множества {х1, х2, ... , хn}.

Определение
Если х — логическая переменная, , то выражение

Алгоритм приведения формулы к ДНФ.
1. Выразить все логические операции, участвующие в построении формулы, через дизъюнкции, конъюнкции и отрицания, используя эквивалентности

Совершенные ДНФ (СДНФ) и КНФ (СКНФ).
Пусть (x1,..., xn) — набор логических переменных, Δ = (δ1,,.., δп) — набор нулей и

Первая теорема Шеннона
Для решения задачи нахождения СДНФ и СКНФ, эквивалентных исходной формуле φ, предварительно рассмотрим разложения булевой функции f(x1, х2

Вторая теорема Шеннона
В силу принципа двойственности для булевых алгебр справедлива Теорема 6.4.3 (вторая теорема Шеннона). Любая булева функция f(x1, х2,...

Функциональная полнота
Теорема(о функциональной полноте). Для любой булевой функции f найдется формула φ, представляющая функцию f

Алгоритм нахождения СДНФ.
Для нахождения СДНФ данную формулу нужно привести сначала к ДНФ, а затем преобразовать ее конъюнкты в конституенты единицы с помощью следующих действий: а) если в конъюнкт входит некоторая

Метод Квайна
Рассмотрим метод Квайна для нахождения МДНФ, представляющей данную булеву функцию. Определим следующие триоперации: - операция полного склеивания -

Каноническое представление логических функций
Каноническими формами логических (формул) функций называются выражения, имеющие стандартную форму булевой формулы такой, которая однозначно представляет логическую функцию. В алгебр

Системы булевых функций
Пусть даны булевы функции f(g1, g2, …, gm) и g1(x1, x2, …, xn), g2(x1

Базис Жегалкина.
Примерю Рассмотрим систему . Она является полной, так как любая функция из стандартного базиса выражается чере

Теорема Поста
Теорема Поста устанавливает необходимые и достаточные условия полноты системы булевых функций. (Post E.L. The two-valued interactive systems of mathematical logic. – Annals of Math. Stu

Доказательство.
Необходимость. От противного. Пусть и

Алгебра Жегалкина
Сумма по модулю 2, конъюнкция и константы 0 и 1 образуют функционально полную систему, т.е. образуют алгебру - алгебру Жегалкина. A = <FB,

ЛОГИКА ВЫСКАЗЫВАНИЙ
Математическая логика изучает базовые понятия синтак­сиса (формы) и семантики (содержания) естественного языка. Рассмотрим три крупных направления исследований в матема­тической логике — логику

Определение предиката
Пусть Х1, Х2, ..., Хп произвольные переменные. Эти переменные будем называть предметными. Пусть наборы переменных вы

Применение предикатов в алгебре
Рассмотрим предикаты, в которых свободной является лишь одна переменная, которую обозначим через х, и обсудим применение предикатов в алгебре. Типичным приме

Булева алгебра предикатов
Так как к предикатам можно применять логические операции, то для них справедливы основные законы булевой алгебры. Теорема. (Свойства логических операций для предикатов). Мн

F↔G=(F→G)(G→F), F→G=неFG.
2. Использовать закон ненеF=F, законы де Моргана: не(F

Исчисление предикатов
Исчисление предикатов называют еще теорий первого порядка. В исчислении предикатов, так же как и в исчислении высказываний, на первом по важности месте стоит проблема разрешимост

Следование и эквиваленция
Высказывательная форма Q2 следу­ет из высказывательной формы Q1, если импликация Q1→Q2 об­ращается в истинное выс

Принятые обозначения
Символы «порядка не более». При сравнении скорости роста двух функций f(n) и g(n) (с неотрицательными значениями) очень удобны следующи

Метаобозначения
Обозна-чения Содержание Пример ИЛИ

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги