Конъюнкция и дизъюнкция реферат

Обновлено: 02.07.2024

Алгебра логики (булева алгебра) – это раздел математики, возникший в XIX веке благодаря усилиям английского математика Дж. Буля. Поначалу булева алгебра не имела никакого практического значения. Однако уже в XX веке ее положения нашли применение в описании функционирования и разработке различных электронных схем. Законы и аппарат алгебры логики стал использоваться при проектировании различных частей компьютеров (память, процессор). Хотя это не единственная сфера применения данной науки.

Что же собой представляет алгебра логики? Во-первых, она изучает методы установления истинности или ложности сложных логических высказываний с помощью алгебраических методов. Во-вторых, булева алгебра делает это таким образом, что сложное логическое высказывание описывается функцией, результатом вычисления которой может быть либо истина, либо ложь (1, либо 0). При этом аргументы функции (простые высказывания) также могут иметь только два значения: 0, либо 1.

Логические операции. Дизъюнкция, конъюнкция и отрицание

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

Алгебра логики предусматривает множество логических операций. Однако три из них заслуживают особого внимания, т.к. с их помощью можно описать все остальные, и, следовательно, использовать меньше разнообразных устройств при конструировании схем. Такими операциями являются конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ). Часто конъюнкцию обозначают &, дизъюнкцию - ||, а отрицание - чертой над переменной, обозначающей высказывание.

При конъюнкции@/a> истина сложного выражения возникает лишь в случае истинности всех простых выражений, из которых состоит сложное. Во всех остальных случаях сложное выражение будет ложно.

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

Отрицание – это унарная операция, т.к выполняется по отношению к одному простому выражению или по отношению к результату сложного. В результате отрицания получается новое высказывание, противоположное исходному.

Для логических величин обычно используются три операции:

Конъюнкция – логическое умножение (И) – and, &, ∧.

Дизъюнкция – логическое сложение (ИЛИ) – or, |, v.

Логическое отрицание (НЕ) – not,.

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

Логические основы компьютера

В ЭВМ используются различные устройства, работу которых прекрасно описывает алгебра логики. К таким устройствам относятся группы переключателей, триггеры, сумматоры.

Кроме того, связь между булевой алгеброй и компьютерами лежит и в используемой в ЭВМ системе счисления. Как известно она двоичная. Поэтому в устройствах компьютера можно хранить и преобразовывать как числа, так и значения логических переменных.

Переключательные схемы

В ЭВМ применяются электрические схемы, состоящие из множества переключателей. Переключатель может находиться только в двух состояниях: замкнутом и разомкнутом. В первом случае – ток проходит, во втором – нет. Описывать работу таких схем очень удобно с помощью алгебры логики. В зависимости от положения переключателей можно получить или не получить сигналы на выходах.

Вентили, триггеры и сумматоры

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

Триггеры и сумматоры – это относительно сложные устройства, состоящие из более простых элементов – вентилей.

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

Сумматоры широко используются в арифметико-логических устройствах (АЛУ) процессора и выполняют суммирование двоичных разрядов.

Свойства информации:

- Объективность (информация объективна, если она не зависит от чьего-либо мнения, суждения);

- Достоверность (информация достоверна, если она отражает истинное положение дел);

- Полнота (информация полна, если ее достаточно для понимания и принятия решения);

- Актуальность (информация актуальна, своевременна, если она важна, существенна для настоящего времени);

- Полезность (оценивается по тем задачам, которые мы можем решить с ее помощью);

- Понятность (информация понятна, если она выражена на языке, доступном для получателя);

- Доступность (информация доступна, если мы можем её получить).

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

Информация проявляется именно в информационных процессах. Информационные процессы всегда протекают в каких-либо системах (социальных, социотехнических, биологических и пр.).

Наиболее обобщенными информационными процессами являются сбор, преобразование, использование информации.

К основным информационным процессам, изучаемым в курсе информатики, относятся: поиск, отбор, хранение, передача, кодирование, обработка, защита информации.

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

Компьютер является универсальным устройством для автоматизированного выполнения информационных процессов.

Человек хранит полученную информацию в голове. Мозг человека – огромное хранилище информации. Блокнот или записная книжка, ваш дневник, школьные тетрадки, библиотека, музей, кассета с записями любимых мелодий, видеокассеты – все это примеры хранения информации.

Информацию можно обрабатывать: перевод текста с английского языка на русский и наоборот, вычисление суммы по заданным слагаемым, решение задачи, раскрашивание картинок или контурных карт – все это примеры обработки информации. Все вы любили в свое время раскрашивать книжки-раскраски. Оказывается, в это время вы занимались важным процессом – обработкой информации, черно-белый рисунок превращали в цветной.

Информацию можно даже терять. Допустим, Иванов Дима забыл дневник дома и поэтому записал домашнее задание на листочке. Но, играя на перемене, он сделал из него самолетик и запустил его. Придя домой, Дима не смог сделать домашнюю работу, он потерял информацию. Теперь ему нужно или попытаться вспомнить, что же ему задали, или позвонить однокласснику, чтобы получить нужную информацию, или идти в школу с невыполненным домашним заданием.

Двоичное кодирование – один из распространенных способов представления информации. В вычислительных машинах, в роботах и станках с числовым программным управлением, как правило, вся информация, с которой имеет дело устройство, кодируется в виде слов двоичного алфавита.

Двоичный алфавит состоит из двух цифр 0 и 1.

Цифровые ЭВМ (персональные компьютеры относятся к классу цифровых) используют двоичное кодирование любой информации. В основном это объясняется тем, что построить техническое устройство, безошибочно различающее 2 разных состояния сигнала, технически оказалось проще, чем то, которое бы безошибочно различало 5 или 10 различных состояний.

К недостаткам двоичного кодирования относят очень длинные записи двоичных кодов, что затрудняет работу с ними.

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Содержание
Конъюнкция и дизъюнкция…………………………………………………………. 2 стр.

Построение минимальных ДНФ…………………………………………………….. 2 стр.

Нахождение сокращенной ДНФ методом Квайна…………………………………. 5 стр.

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

Дизъюнктивная нормальная форма(ДНФ)

Определение 3: Переменная или называется литералом (или буквой).
Определение 4: Конъюкция литералов, встречающихся не более чем по одному разу, называется элементарной конъюнкцией. Число букв входящих в неё называется её рангом. Элементарная конъюнкция называется полной относительно рассматриваемой булевой функции, если её ранг равен числу переменных данной функции.
Определение 5: Дизъюнкция конечного множества элементарных конъюнкций называется дизъюнктивной нормальной формой(ДНФ). Число элементарных конъюнкций, образующих дизъюнктивную нормальную форму(ДНФ) называется длиной ДНФ. ДНФ содержащая только полные элементарные конъюнкции называется совершенной ДНФ(или СДНФ). Любую логическую формулу А можно представить в виде ДНФ, а затем ДНФ в виде СДНФ.
Конъюнктивная нормальная форма(КНФ)

Определение 6: Дизъюнкция литералов, встречающихся не более чем по одному разу, называется элементарной дизъюнкцией. Число литералов является рангом дизъюнкции. Элементарная дизъюнкция содержащая максимальное число литералов называется полной.
Определение 7: Конъюнкция конечного множества элементарных дизъюнкций называется конъюнктивной нормальной формой(или сокращенно КНФ). Число элементарных дизъюнкций образующих КНФ называется длинной. КНФ состоящая только из полных элементарных дизъюнкций называется СКНФ. Произвольную формулу B v можно представить в виде КНФ, а затем КНФ в виде СКНФ.
Построение минимальных ДНФ.

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

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

В общем случае можно определить операцию склеивания для различных элементарных конъюнкций, имеющих общий множитель из (n-L) букв, где n - число переменных, из которых состоит элементарная конъюнкция. Например, после вынесения общего множителя за скобки в ДНФ

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

Заметим, что по результату склеивания можно всегда восстановить исходную совокупность элементарных конъюнкций. Восстановление выполняется с использованием последовательных действий, которые назовем операцией расширения. Эта операция выполняется путем умножения конъюнкции, полученной в результате склеивания, на дизъюнкцию каждой отсутствующей буквы и ее отрицания. Например, чтобы восстановить заданную ДНФ по конъюнкции полученной в предыдущем примере, необходимо домножить ее на произведение. В результате получаем.

Назовем число букв, образующих конъюнкцию, рангом конъюнкции. Для обозначения ранга конъюнкции K условимся использовать выражение r(K). Отметим, что склеиваться могут только конъюнкции одинакового ранга. Между конъюнкциями различных рангов может существовать отношение покрытия. Если r(Ki)

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

Отыскивая склеивающиеся конъюнкции в множестве (φ) и выполняя операцию склеивания, находим множество конъюнкций второго ранга:

Поскольку последнее множество состоит из одной конъюнкции, то (φ) = ∅ . Объединим полученные множества конъюнкций различных рангов в одно множество R(φ) и назовем его комплексом конъюнкций заданной функции φ: . Любое подмножество , конъюнкции которого покрывают все элементарные конъюнкции множества (φ), назовем покрытием заданной функции φ. Например, следующие три подмножества являются покрытиями заданной функции:

Каждое покрытие соответствует ДНФ заданной переключательной функции. Таким образом, множество различных покрытий определяет множество эквивалентных дизъюнктивных нормальных форм переключательной функции φ.

Дизъюнктивную нормальную форму, обладающую наименьшим рангом из всех ДНФ заданной переключательной функции, назовем минимальной дизъюнктивной нормальной формой (МДНФ). В рассматриваемом примере МДНФ соответствует покрытию и имеет вид. Ранг этой ДНФ равен восьми.

Анализируя элементы комплекса R(φ), можно заметить, что некоторые из них покрываются конъюнкциями меньшего ранга и что имеются элементы, которые не покрываются другими конъюнкциями. Это наблюдение позволяет нам сформулировать следующее определение. Конъюнкция K называется минималью или простым импликантом, если в комплексе R(φ) не существует другой конъюнкции K' меньшего ранга, которая покрывает конъюнкцию K. Например, множество минималей S функции, приведенной в примере 3.1, имеет вид:

Дизъюнктивная форма, соответствующая множеству минималей, называется сокращенной дизъюнктивной нормальной формой (СкДНФ). Используя определение минимали, сформулируем следующую теорему.
Теорема 3.1. Любая минимальная дизъюнктивная нормальная форма состоит из минималей.
Доказательство.

Допустим, что форма L является МДНФ функции φ и что в нее входит конъюнкция K, которая не является минималью. Тогда, согласно определению минимали, в комплексе R(φ) должна существовать конъюнкция меньшего ранга K', которая покрывает K и является минималью. Поскольку K' покрывает K, то она покрывает все элементарные конъюнкции, покрываемые K, и, следовательно, в форме L можно конъюнкцию K заменить конъюнкцией K'. Обозначим ДНФ, полученную после такой замены, L. Формы L и L' отличаются только одной конъюнкцией, причем r(K) > r(K'). Следовательно, r(L) > r(L'). Итак, наше предположение о том, что L является МДНФ и содержит конъюнкцию, не являющуюся минималью, является неверным, что и доказывает справедливость теоремы.

Приведенная теорема дает нам основание при построении МДНФ работать с множеством минималей S вместо того, чтобы выполнять это построение, пользуясь элементами комплекса R(φ), который содержит, как правило, значительно большее число элементов, чем S. Необходимо отметить, что ранг СкДНФ может намного превышать ранг МДНФ, поэтому построение СкДНФ следует рассматривать как первый этап процедуры нахождения МДНФ заданной функции. Задачей второго этапа этой процедуры обычно является упрощение полученной СкДНФ, которое достигается за счет удаления избыточных конъюнкций из СкДНФ.

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

Этот метод основан на преобразовании ДНФ с помощью операций полного и неполного склеивания и операции поглощение.
Полное склеивание.

Пусть х-булева переменная, а β - элементарная конъюнкция. Тогда имеет

Для доказательства этого соотношения преобразуем его левую часть, используя свойство дистрибутивности конъюнкции относительно дизъюнкции и равенства х ∨ х=1, 1 ⋅ х=х.

хβ ∨ хβ = ( х ∨ х) ⋅ β = 1 ⋅ β = β .
Неполное склеивание

Имеет место соотношение
хβ ∨ хβ=β ∨ хβ ∨ хβ. (11)
Для доказательства (11) заменим в соотношении u=u∨ u высказывание u на хβ ∨ хβ. Получим

хβ ∨ хβ=( хβ ∨ хβ) ∨ (хβ ∨ хβ).
Поглощение.
Наряду с конъюнкцией β рассмотрим еще одну элементарную конъюнкцию γ. Тогда имеет место соотношение
β∨β ⋅ γ=β (12)
Преобразуем левую часть (12). Имеем

β∨β ⋅ γ=β ⋅ 1∨β ⋅ γ=β ⋅ (β∨γ)=β ⋅ 1=β

В случае полного склеивания (10) говорят, что члены хβ и хβ клеиваются по х , а случае поглощения (12) говорят, что член β ⋅ γ поглощается членом β.

Приведем алгоритм построения сокращенной ДНФ по методу Квайна.

1. Найдем совершенную ДНФ заданной функции f.

2. Привести в полученной ДНФ все конъюнктивные члены к одному рангу n.

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

4. Провести все возможные операции поглощения, в результате чего получим ДНФ, состоящую из элементарных конъюнкций ранга n-1.

5. В полученной ДНФ провести все возможные операции склеивания и поглощения в соответствии с пунктами 3,4. В результате получим ДНФ, состоящую из элементарных конъюнкций ранга n-2.

6. Описанную выше процедуру следует проводить до тех пор, пока это

будет возможно. Полученная в итоге ДНФ и будет сокращенной. Образующие

ее элементарные конъюнкции называются простыми импликантами функции f.

Пример. Найти сокращенную ДНФ булевой функции

f(x,y,z) = xz ∨ xyz ∨ xyz ∨ xyz.

1. Прежде всего приведем все конъюнктивные члены к одному и тому же рангу r=3. Для этого умножим первый член xz на y∨ y=1 . Имеем

xz = xz1 = xz(y ∨ y) = xzy ∨ xzy = xzy ∨ xzy.

Тогда исходная функция f примет вид

f(x,y,z)=xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz (13)

2. Приведем все возможные операции неполного склеивания в два приема:

а) склеим (полное склеивание) каждую из конституент единицы ДНФ (13) с последующими.
1-ый член склеивается со 2-м по y, получим xz,

2-й ни с чем не склеивается,

3-й член склеивается с 4-м по y, получим xz,

f(x,y,z)=xz ∨ yz ∨ xz ∨ xy ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz

3. Проведем все возможные операции поглощения в соответствии с формулой β∨β ⋅ γ=β . Первый член xz поглощает xyz и xyz, т.е.

xz ∨ xyz = xz ∨ (xz)y =xz ,

xz ∨ xyz = xz ∨ (xz)y =xz .

Аналогичным образом член yz поглощает xyz. Далее, xz поглощает xyz и xyz. В итоге получим

f(x,y,z)=xz ∨ yz ∨ xz ∨ xy. (14)

4. Непосредственной проверкой убеждаемся, что применение операций склеивания и поглощения невозможно. Полученное соотношение (14) является сокращенно ДНФ заданной функции. Конъюнктивные члены (14) представляют собой простые импликанты функции f.

Информатика

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

Логика применима для решения задач по геометрии, физике, теории вероятности, понимания некоторых противоречивых речевых оборотов и сложных для непрофессионала научных текстов. Для понимания терминов и сферы их применимости изучим несколько вспомогательных понятий:

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

A	B	F
1	1	1
1	0	0
0	1	0
0	0	0

Если одно из выражений ложное, то света в комнате не будет.

Дизъюнкция, логическое сложение, которое подчиняется правилам математического сложения. Если одно из слагаемых истина (то есть 1) то результат получается 1 (в математике также возможен результат 2, но в логике обозначаем 1, как истинное выражение). Если оба исходных понятия ложные (0), то и результат не может быть истиной (1). Таблица для дизъюнкции выглядит так:

A	B	F
1	1	1
1	0	1
0	1	1
0	0	0

А формула принимает вид: F = A + B.

А	В	F
1	1	1
1	0	0
0	1	1
0	0	1

Эквивалентность — операция в логике, при которой истина получается только в том случае, если обе части выражения истинны:

A	B	F
1	1	1
1	0	0
0	1	0
0	0	1

В сложном логическом выражении существует определенный порядок выполнения операций:

Напомним вначале понятие положительной функции. Функция / называется положительной, если она принимает положительные значения при всех значениях аргумента из области определения: fxe Df (f (x)>Q). Операции + и • связаны дистрибутивным (или распределительным) законом: а (Ь+с) = аЬ+ас. Говорят, что умножение дистрибутивно относительно сложения. Таким образом, исходное предложение можно… Читать ещё >

математика: логика
теория множеств и комбинаторика

Свойства операций конъюнкции и дизъюнкции ( реферат , курсовая , диплом , контрольная )

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

a+b = b+a> a-b = b-a. Это свойство называют коммутативным (или переместительным) законом.

(a+b)+c = a+(b+c), (ab)-c = а (Ь-с). Это свойство называют ассоциативным (или сочетательным) законом.

Операции + и • связаны дистрибутивным (или распределительным) законом: а (Ь+с) = аЬ+ас. Говорят, что умножение дистрибутивно относительно сложения.

Однако, поменяв в равенстве местами знаки + и •, получим равенство а+(Ь-с) = (а+Ь) (а+с), не являющееся тождеством. Контрпример: а= 1, Ь=2, с=3, тогда а+(Ь-с) = 1+2−3 = 7, но (а+Ь)(а+с) = (1+2)-(1+3) = 12. Таким образом, сложение не дистрибутивно относительно умножения.

Для конъюнкции и дизъюнкции справедливы все указанные выше свойства, при этом каждая из операций конъюнкции и дизъюнкции дистрибутивна по отношению к другой операции. Запишем указанные законы и приведем ряд других.

1°. Коммутативные законы. АлВ = ВлА, AvB = BvA.
2°. Ассоциативные законы. (АлВ)лС = Лл (ВлС), (AvB)vC = Av (BvC).
3°. Дистрибутивные законы:

Av (BaC) = (AvB)a (AvC) — дистрибутивность дизъюнкции относительно конъюнкции.

4°. Законы идемпотентности: АлА = A, AvA = А.
5°. Законы поглощения: Aa (AvB) = А, Av (AaB) = А.
6°. Законы с константами: 4 vw = м, 4aw = 4,4v.7 = 4, 4а 7 = л.

Вместо букв А, В и С можно подставлять любые формулы.

Пример 3.3.1. Рассмотрим формулу (^>0)v ((^2)a (.y>0)).

Запишите символически определения возрастающей и убывающей функций.

Исходное предложение выражается формулой (AaB)v (AaC). По закону 3° эта формула равносильна Aa (BvC).

Рассмотрим взаимосвязь операций конъюнкции и дизъюнкции с кванторными операциями.

Пример 3.3.3. Определим значения двух формул:

Сформулируем предложения, выражаемые этими формулами.

Предложение Р истинно, так как всякое действительное число попадет в интервал (-оо; 1) или (0; +оо), поскольку их объединение даст все множество R.

Предложение Q ложно, так как оба высказывания УдгеН (д>0) и VagR (x

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

Читайте также: