Алгебра логики распределительный закон к отрицанию

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

Работа добавлена на сайт samzan.ru: 2021-06-20

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

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

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

Переместительный закон

Формулировка: логические переменные можно менять местами. Возможные варианты записи:

и

Сочетательный закон

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

Распределительный закон

Формулировка: одинаковые переменные в конъюнкциях и дизъюнкциях можно выносить за скобки. Закон имеет две модификации. Первая модификация называется распределением конъюнкции по дизъюнкции. Форма записи закона в первой модификации:

Вторая модификация закона называется распределением дизъюнкции по конъюнкции. Форма записи закона во второй модификации:

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

Закон отрицания (инверсии)

Закон отрицания имеет две формулировки. Первая: отрицание от конъюнкции равно дизъюнкции отрицаний переменных. Форма записи:

Вторая формулировка: отрицание от дизъюнкции равно конъюнкции отрицаний переменных. Формы записи:

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

Тождественные соотношения

Тождественные соотношения проверяются подстановкой возможных значений логических переменных. Основные тождественные соотношения:

1)

2)

3)

4)

5)

6)

7)

В тождествах 6, 7, 8 символом F обозначена любая логическая функция или переменная.

Следствия из законов алгебры логики

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

Она содержит наименьшее количество конъюнкций минимально возможного ранга. Минимальная логическая функция не поддается дальнейшему упрощению. Для минимизации логических функций используются следующие правила: поглощения, свертки, расширения и склеивания.

Рассмотрим эти правила.

Правило поглощения

Данное правило является следствием из распределительного закона. Оно может быть записано в следующем виде:

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

При  получаем

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

Правило свертки

Правило является следствием второго распределительного закона. Запись правила:

а)

б)

Доказательство. К левой части выражения применяется второй распределительный закон, т. е.

Первая скобка правой части равна единице, поэтому . Также доказывается равенство .

Правило расширения

Правило записывается в следующем виде:

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

Правило склеивания

Правило склеивания базируется на понятии соседних конъюнкций. Соседними называются конъюнкции, отличающиеся представлением одной переменной. Например, конъюнкции  являются попарно соседними. В первой паре конъюнкции отличаются представлением x2, а во второй — представлением x1. По этим переменным конъюнкции склеиваются.

Формулировка правила: две соседние конъюнкции склеиваются с образованием одной конъюнкции меньшего ранга; исчезает та переменная, по которой конъюнкции склеиваются.

Пример: Задана логическая функция в СДНФ .

Необходимо упростить функцию. Так как конъюнкции функции соседние и отличаются представлением x1 то путем их склеивания получаем . Справедливость преобразования (склеивания) доказывается вынесением общих переменных в конъюнкциях за скобку, т. е.

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

1. инверсия

2. конъюнкция

3. дизъюнкция

4. равнозначность.

Типовые задачи по преобразованию логических функций

Задачи по преобразованию логических функций весьма разнообразны. Однако их можно подразделить на следующие типовые группы:

• упрощение логических функций, заданных различным образом;

• построение таблиц истинности функций;

• вычисление значения логического выражения для заданного набора значений переменных;

• определение тождественности логических функций.

I. Функция задана в произвольной форме

Пример 1. Упростить логическую функцию, заданную выражением

а) Приведение функции к ДНФ путем использования законов и правил, т. е.

б) Вычеркивание конъюнкций, равных нулю.

Конъюнкция , конъюнкции равны нулю, поэтому получаем упрощенную функцию

Пример 2. Упростить логическую функцию, заданную выражением

а) Применение закона отрицания с целью последующего перехода к ДНФ, т. е.

б) Анализ промежуточного результата. Устанавливаем, что первая скобка равна единице, так как  и , где .

Окончательно получаем .

Пример 3. Упростить логическую функцию, заданную выражением

а) Упрощение функции путем использования закона отрицания и перемножения скобок

б) Применение правила расширения:

1. из группы конъюнкций  исключаем ;
2. из группы конъюнкций  исключаем ;
3. из группы конъюнкций  исключаем .

Окончательно получаем:

Покажем, что если применять другую последовательность исключения лишних конъюнкций, можно получить другой вид функции, которая не поддается дальнейшему упрощению.

Применяем правило расширения в следующей последовательности:

1. из группы конъюнкций  исключаем ;
2. из группы конъюнкций  исключаем

В результате получаем . Эта функция по рассмотренным правилам и законам упрощению не поддается.

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

II. Функция задана таблицей истинности

Пример 4. Упростить функцию , равную единице на наборах 3, 5, 6, 7 (011, 101, 110, 111).

а) Построение таблицы истинности (схема 1а).

В первых трех столбцах записываются возможные наборы. В столбце F на наборах 011, 101, 110 и 111 проставляются единицы; на остальных наборах проставляются нули.

б) Запись функции в СДНФ (см. правило записи).

Наборам 011,101,110,111 соответствуют конъюнкции

поэтому функция будет записана в следующем виде:

в) Упрощение функции. Функции, записанные в СДНФ, первоначально упрощаются по правилу склеивания. Затем применяются другие правила и тождественные соотношения.

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

После склеивания пар соседних конъюнкций окончательно получим

Можно было не подписывать конъюнкцию , а просто склеить поочередно три первые конъюнкции с четвертой конъюнкцией.

Построение таблиц истинности функций

Пример 5. Построить таблицу истинности функции: .

а) Запись заданной функции в СДНФ.

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

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

Так как по правилу записи конъюнкций в СДНФ единице в наборе соответствует переменная, а нулю — ее отрицание, то конъюнкциям  соответствуют наборы 111, 110, 011, 001, т. е. 7, 6, 3, 1.

в) Непосредственное построение таблицы.

В столбце F таблицы (см. схему 1б) на наборах 111, 110, 011, 001 проставляются единицы, а на остальных наборах ставятся нули.

Вычисление значения логического выражения для заданного набора значений переменных

Для вычисления значения логического выражения на заданном наборе значений переменных можно применять два способа: использование СДНФ и способ подстановки. Рассмотрим первый из них.

Пример 6. Вычислить значение логического выражения  при х=1, у=1, z=0, т. е. на наборе 6, или 110.

а) Получение СДНФ заданной функции (см. выше пример 4):

После исключения повторяющейся конъюнкции получаем

б) Определение значения выражения.

Выражение V принимает единичное значение только на наборах 100, 000 и 101, или 4, 0, 5 так как задан набор 6, то логическое выражение принимает нулевое значение (V=0).

Второй способ не нуждается в особых пояснениях. При заданных значениях х=1, у=1 и z=0 имеем . Подставляем эти значения в выражение и получаем

В случае вычисления значений сложных логических выражений второй способ не исключает ошибок.

Определение тождественности логических функций

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

Пример 7. Проверить тождественность логических функций:

а) Упрощение функции F.

Применяем закон отрицания и перемножаем скобки, т. е.

Во второй скобке конъюнкции  склеиваются, поэтому получаем

Переменная  поглощает конъюнкцию , что дает

или

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

б) Преобразование функции f.

Функция f также записана в СДНФ. Так как СДНФ функций F и f не совпадают, то они не являются тождественными.

в) Преобразование функции Р.

Получена СДНФ функции Р. Функции F и Р являются тождественными, так как имеют одинаковые СДНФ.

Пример 8. Проверить тождественность логических функций

которая принимает единичные значения на наборах 2, 3.

а) Упрощение функции F. Применяется закон отрицания

Во второй скобке переменная  поглощает конъюнкцию , что приводит к следующему результату:

Во второй скобке используется правило свертки и затем скобки перемножаются:

б) Получение СДНФ функции F.

в) Получение СДНФ функции f.

Так как функция f принимает единичные значения на наборах 2 и 3, то ее СДНФ будет иметь вид

Функции F и f имеют одинаковые СДНФ, следовательно, они тождественны.

Пример 9. Проверить тождественность логических функций:

Функция f имеет следующую минимальную форму .

а) Упрощение функции F.

Перемножение скобок:

Исключение лишней конъюнкции  из группы :

Исключение лишней конъюнкции yz из группы :

В результате получаем

Упрощенная форма функции F и минимальная форма функции f не совпадают. Однако это не значит что функции не тождественны. Для окончательного вывода нужно получить СДНФ обеих функций.

б) Получение СДНФ функции F.

После удаления повторяющихся конъюнкций получаем

в) Получение СДНФ функции f:

Функции F и f имеют одинаковые СДНФ и принимают единичные значения на одних и тех же наборах 0, 1, 3, 4, 6, 7. Эти функции тождественны. Так как минимальные формы функций не совпадают, то можно сделать вывод, что для функции F была получена тупиковая форма.

Задачи для самостоятельного решения

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

Задача. Получить кратчайшую форму записи логической функции трех переменных

Источник: http://samzan.ru/150875

Алгебра логики – основные законы, свойства и формулы раздела информатики

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

Что такое алгебра и алгебра логики

Алгебра — это раздел математики, который обобщенно можно охарактеризовать, как расширение и обобщение арифметики.

Алгебра логики — это раздел математической логики, который исследует операции над высказываниями.

Законы алгебры логики

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

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

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

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

Закон двойственности и инверсии (закон Моргана) – основоположником данного правила стал шотландский математик и логик де Морган. Он разработал правило, которое связывает логические операции конъюкцию (И) и дизъюнкцию (ИЛИ) с помощью отрицания.

Основные законы алгебры логики представлены в таблице:

Логические выражения

В информатике предоставляется два вида высказываний: простое и сложное. 

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

Примеры:

• Нью-Йорк — столица США (ложное);
• в России 1117 городов (верное).

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

Пример:

Идёт дождь, а у меня нет зонта.

Основные логические операции

Логические процессы подразделяются на несколько классов. Рассмотрим их последовательно.

Логическое отрицание (инверсия) —НЕ

Данная операция используется при обозначении отрицания. Она обозначается знаками — NO, NOT, ! В=2 (истина), а после выполнения операции отрицания, В, к примеру, приобретет значение 1 (ложное).

Таблица истинности инверсии:

Результаты операции НЕ следующие:

• если исходное выражение истинно, то результат его отрицания будет ложным;
• если исходное выражение ложно, то результат его отрицания будет истинным. 

Логическое сложение (дизъюнкция, объединение) — ИЛИ

Понятие «Логическое ИЛИ» также можно заменить понятием «Дизъюнкция». Данная операция обозначается знаками — ИЛИ, OR, ||, |. 

Но есть небольшое отличие: в «Логическом И» результат отрицания равен единице, если оба обозначения равны единице, а в «Логическом ИЛИ» итог равен единице, если одно из обозначений равно единице.

Таблица истинности операции ИЛИ:

Логическое умножение(конъюнкция) — И

В истории данная операция также обозначается как логическое умножение и конъюнкция. Данная операция обозначается элементами — И, AND, &&, &.

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

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

Таблица истинности операции И приведена ниже:

Логическое следование (импликация) — ЕСЛИ ТО

Данная программа имеет также название «Импликация». Она образуется из двух высказываний, которые соединяет: «если…, то».

Необходимо запомнить, что данная операция ложна только тогда, когда из первого ложного утверждения следует ложный итог. На компьютерном языке данный процесс обозначается формулой: if…then.

Таблица истинности операции ЕСЛИ ТО выглядит так:

Операция эквивалентности (равнозначности) – А ТОГДА И ТОЛЬКО ТОГДА, КОГДА В

Данная операция определяется так: сложное высказывание будет истинно тогда и только тогда, когда и А, и В — истинные.

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

Таблица истинности операции эквивалентности:

Источник: https://nauka.club/informatika/algebra-logiki.html

Основы алгебры логики

Законы алгебры высказываний

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

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

Законы алгебры высказываний (алгебры логики) — это тавтологии.

Иногда эти законы называются теоремами.

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

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

Закон тождества:

А=А

Всякое понятие и суждение тождественно самому себе.

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

Например, рассуждение Правильно говорят, что язык до Киева доведет, а я купил вчера копченый язык, значит, теперь смело могу идти в Киев неверно, так как первое и второе слова «язык» обозначают разные понятия.

В рассуждении: Движение вечно. Хождение в школу — движение. Следовательно, хождение в школу вечно слово «движение» используется в двух разных смыслах (первое — в философском смысле — как атрибут материи, второе — в обыденном смысле — как действие по перемещению в пространстве), что приводит к ложному выводу.

Закон непротиворечия:

В один и тот же момент времени высказывание может быть либо истинным, либо ложным, третьего не дано. Истинно либо А, либо не А. Примеры выполнения закона исключенного третьего:

1. Число 12345 либо четное, либо нечетное, третьего не дано.

2. Предприятие работает убыточно или безубыточно.

3. Эта жидкость является или не является кислотой.

Закон исключенного третьего не является законом, признаваемым всеми логиками в качестве универсального закона логики. Этот закон применяется там, где познание имеет дело с жесткой ситуацией: «либо — либо», «истина—ложь». Там же, где встречается неопределенность (например, в рассуждениях о будущем), закон исключенного третьего часто не может быть применен.

Рассмотрим следующее высказывание: Это предложение ложно. Оно не может быть истинным, потому что в нем утверждается, что оно ложно. Но оно не может быть и ложным, потому что тогда оно было бы истинным. Это высказывание не истинно и не ложно, а потому нарушается закон исключенного третьего.

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

Кто стрижет волосы парикмахеру? В логике из-за ее формальности нет возможности получить форму такого ссылающегося самого на себя высказывания. Это еще раз подтверждает мысль о том, что с помощью алгебры логики нельзя выразить все возможные мысли и доводы.

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

Например, определим, чему эквивалентно (равносильно) А (двойное отрицание А, т. е. отрицание отрицания А).Для этого построим таблицу истинности:

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

Таким образом, мы можем сформулировать закон двойного отрицания:

Если отрицать дважды некоторое высказывание, то в результате получается исходное высказывание. Например, высказывание А = Матроскин — кот эквивалентно высказыванию А = Неверно, что Матроскин не кот.

Аналогичным образом можно вывести и проверить следующие законы:

Свойства констант:

Законы идемпотентности:

Сколько бы раз мы ни повторяли: телевизор включен или телевизор включен или телевизор включен … значение высказывания не изменится. Аналогично от повторения на улице тепло, на улице тепло,… ни на один градус теплее не станет.

Законы коммутативности:

A v B = B v A

А & В = В & А

Операнды А и В в операциях дизъюнкции и конъюнкции можно менять местами.

Законы ассоциативности:

A v(B v C) = (A v B) v C;

А & (В & C) = (A & В) & С.

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

Законы дистрибутивности:

A v (B & C) = (A v B) &(A v C)

(дистрибутивность дизъюнкции
относительно конъюнкции)

А & (B v C) = (A & B) v (А & C)

(дистрибутивность конъюнкции
относительно дизъюнкции)

Закон дистрибутивности конъюнкции относительно дизъюнкции ана­логичен дистрибутивному закону в алгебре, а закон дистрибутивности дизъюнкции относительно конъюнкции аналога не имеет, он справедлив только в логике. Поэтому необходимо его доказать. Доказательство удобнее всего провести с помощью таблицы истинности:

Законы поглощения:

A v (A & B) = A

A & (A v B) = A

Проведите доказательство законов поглощения самостоятельно.

Законы де Моргана:

Словесные формулировки законов де Моргана:

1.

2.

Мнемоническое правило: в левой части тождества операция отрицания стоит над всем высказыванием. В правой части она как бы разрывается и отрицание стоит над каждым из простых высказываний, но одновременно меняется операция: дизъюнкция на конъюнкцию и наоборот.

Примеры выполнения закона де Моргана:

1) Высказывание Неверно, что я знаю арабский или китайский язык тождественно высказыванию Я не знаю арабского языка и не знаю китайского языка.

2) Высказывание Неверно, что я выучил урок и получил по нему двойку тождественно высказыванию Или я не выучил урок, или я не получил по нему двойку.

Замена операций импликации и эквивалентности

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

Так, заменить операцию импликации можно в соответствии со следующим правилом:

Для замены операции эквивалентности существует два правила:

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

Знание правил замены операций импликации и эквивалентности помогает, например, правильно построить отрицание импликации.

Рассмотрим следующий пример.

Пусть дано высказывание:

Е = Неверно, что если я выиграю конкурс, то получу приз.

Пусть А = Я выиграю конкурс,

В = Я получу приз.

Тогда

Отсюда, Е = Я выиграю конкурс, но приз не получу.

Пропустить Навигация

• В начало
  • Страницы сайта
    • Теги
    • Календарь
    • Новости сайта

  • Курсы

    • Дистанционные курсы
    • Школьные площадки
      • Волжский район
      • Заводской район
      • Кировский район
      • Ленинский район
      • Октябрьский район
      • Фрунзенский район
      • ОУ городского подчинения и ГБУ
      • Саратовская область
        • Александрово – Гайский район
        • Аткарский район
        • Балаковский район
        • Балашовский район
        • Вольский район
        • Воскресенский район
        • Дергачевский район
        • Духовницкий район
        • Екатериновский район
        • Ершовский район
        • Ивантеевка
        • Калининский район
        • Красноармейский район
        • Краснокутский район
        • Лысогорский район
        • Марксовский район
        • Новобурасский район
        • Новоузенский район
        • Озинский район
        • Перелюбский район
        • Петровский район
        • Пугачевский район
        • Ровенский район
        • Ртищево
        • Саратовский район
        • Самойловский район
        • Советский район
        • Татищевский район
        • Хвалынский район
        • Энгельсский район
        • МОУ “СОШ №12 г. Шиханы”
        • Турковский район
        • ЗАТО “Светлый”

      • СОИРО

    • Дистанционное обучение детей-инвалидов

    • О портале

    • Нормативные документы

    • Системы дистанционного образования

    • конференция

    • Семинары

    • Региональный Краеведческий марафон “Саратовская кр…

    • Областной конкурс видео и дистанционных курсов “До…

    • Виртуальный исторический класс

    • Методическое объединение дистанционных педагогов

    • Региональная инновационная площадка

    • Областной Фестиваль-конкурс “Экология и Я”

    • Президентские состязания

Пропустить Специальные возможности

Page 3

Пропустить Навигация

• В начало
  • Страницы сайта
    • Теги
    • Календарь
    • Новости сайта

  • Курсы

    • Дистанционные курсы
    • Школьные площадки
      • Волжский район
      • Заводской район
      • Кировский район
      • Ленинский район
      • Октябрьский район
      • Фрунзенский район
      • ОУ городского подчинения и ГБУ
      • Саратовская область
      • СОИРО

    • Дистанционное обучение детей-инвалидов

    • О портале

    • Нормативные документы

    • Системы дистанционного образования

    • конференция

    • Семинары

    • Региональный Краеведческий марафон “Саратовская кр…

    • Областной конкурс видео и дистанционных курсов “До…

    • Виртуальный исторический класс

    • Методическое объединение дистанционных педагогов

    • Региональная инновационная площадка

    • Областной Фестиваль-конкурс “Экология и Я”

    • Президентские состязания

Пропустить Специальные возможности

Источник: https://edusar.soiro.ru/mod/page/view.php?id=6094

Алгебра логики распределительный закон к отрицанию

Например, относительно предложений «Великий русский учёный М. В. Ломоносов родился в 1711 году» и «Two plus six Is eight» можно однозначно сказать, что они истинны. Предложение «Зимой воробьи впадают в спячку» ложно.

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

Но не всякое повествовательное предложение является высказыванием.

Например, предложение «Это предложение является ложным» не является высказыванием, так как относительно него нельзя сказать, истинно оно или ложно, без того, чтобы не получить противоречие. Действительно, если принять, что предложение истинно, то это противоречит сказанному. Если же принять, что предложение ложно, то отсюда следует, что оно истинно.

Относительно предложения

«Компьютерная графика — самая интересная тема в курсе школьной информатики»

также нельзя однозначно сказать, истинно оно или ложно.

Законы поглощения алгебра логики

Закон контрапозиции: (A ? B) = (B ? A). Для логических переменных справедливы и общематематические законы.

Для простоты записи приведем общематематические законы для трех логических переменных A, В и С: 1. Коммутативный закон: A & B = B & A; A ? B = B ? A. 2. Ассоциативный закон: A & (B & C) = (A & B) & C; A ?

(B ? C) = (A ? B) ? C. 3. Дистрибутивный закон: A & (B ?

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

В алгебре логики на основе принятого соглашения установлены следующие правила (приоритеты) для выполнения логических операций: первыми выполняются операции в скобках, затем в следующем порядке: инверсия (отрицание), конъюнкция ( & ), дизъюнкция (v), импликация (?), эквиваленция (?) Выполним преобразование, например, логической функции применив соответствующие законы алгебры логики.

Основные законы алгебры логики

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

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

).

(законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами); 2.

(применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией); 3.

Законы алгебры логики

Нарушитель правил движения.

Свидетели автотранспортного происшествия заявили следующее: Иванов сообщил, что нарушитель ехал на красных Жигулях, Петров сказал, что на синем Запорожце, а Сидоров утверждал, что на мотоцикле, но не красном.

Известно, что каждый из них был в чем-то не прав. На чем проехал нарушитель? Обозначим высказывания: Ж ‑ это были жигули, К-машина красная, С – машина синяя, З – это был запорожец, М – это был мотоцикл.

Тогда каждый свидетель имел истинное составное высказывание: Ж&КvЖ&К, С&ЗvС&З, М&КvМ&К.

Одновременно не может быть два истинных цвета и марки: К&С=0,Ж&З=0, М&Ж=0, М&З=0.

Логическое произведение высказываний свидетелей должно быть истинным: (Ж&КvЖ&К) &(С&ЗvС&З)&( М&К vМ&К)= Ж&К&С&З&М&К v Ж&К&С&З&М&К v Ж&К&С&З&М&К v Ж&К&С&З&М&К v Ж&К&С&З&М&К v Ж&К&С&З&М&К v Ж&К&С&З&М&К v Ж&К&С&З &М&К= 0 v 0 v Ж&К&С&З&М&К

_02Л_Законы АЛ

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

Эти специфичные случаи и формулируются как распределительный закон булевой алгебры: —для конъюнкции конъюнкция переменной и дизъюнкции эквивалентна дизъюнкции конъюнкций; —для дизъюнкции (a vb)(a vc)=a v bc, дизъюнкция переменной и конъюнкции равносильна конъюнкции дизъюнкций этой переменной с сомножителями.

Справедливость распределительного закона для дизъюнкции докажем следующими простейшими преобразованиями: (a vb)(a vc)= (aa v ac v ab v bc)=a v a(b v c)v bc=a(1 v (b v c)) v bc . В результате получаем (avb)(avc)=avbc, так как 1 v (bv c)=1 независимо от выражения в скобках. —для дизъюнкции отрицание дизъюнкции логических переменных эквивалентно конъюнкции отрицаний этих переменных;

3.

Основные законы математической логики.

Пример.

Упростить логическое выражение:

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

Источник: https://27advokat.ru/algebra-logiki-raspredelitelnyj-zakon-k-otricaniju-48094/

Информатика

Понятие — форма мышления, в которой отражаются существенные отличительные признаки предметов.

Понятие имеет две основные логические характеристики: содержание и объем.

м понятия называется совокупность существенных признаков, отраженных в этом понятии.

Объем понятия — это множество предметов, каждому из которых принадлежат признаки, относящиеся понятия.

Совместимые и несовместимые понятия

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

Отношения совместимых понятий:

l  пересечение (часть элементов объема каждого понятия входит в объем другого понятия); например, «мальчик»–«болельщик»;

l  тождество (полное совпадение объемов понятий);

l  подчинение (объем одного понятия полностью входит в объем другого); например, «акула»–«рыба».

Отношения несовместимых понятий:

l  соподчинение; например, «рыба»–«птица» (соподчинены понятию «животное»);

l  противоположность (объект, не попадающий под одно понятие, может не попадать и под другое); например, «черный»–«белый»;

l  противоречие (объект принадлеит объему либо одного, либо другого понятия); например, «светящийся объект»–«несветящийся объект».

Высказывание

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

Высказывание характеризуется своим содержанием и формой.

Умозаключение

Умозаключение — форма мышления, посредством которой из одного или нескольких высказываний, называемых посылками, мы по определенным правилам вывода получаем заключение.

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

Логические операции

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

Инверсия (отрицание)

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

В выражениях обозначается ¬A или Ā.

Читается «НЕ» (например, «не А»).

Конъюнкция (логическое умножение)

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

В выражениях обозначается AÙ B или A&B (знак может не указываться — AB).

Читается «И» (например, «А и Б»)

Дизъюнкция (логическое сложение)

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

В выражениях обозначается AÚ B, иногда A+B.

Читается «ИЛИ» (например, «А или Б»)

Импликация (следование)

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

В выражениях обозначается A Þ B или A ® B.

Читается «ЕСЛИ…ТО» (например, «если А, то Б»)

Эквивалентность (равнозначность)

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

В выражениях обозначается A Û B или A º B.

Читается «ТОГДА И ТОЛЬКО ТОГДА, КОГДА» (например, «А тогда и только тогда, когда Б»)

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

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

Число комбинаций (строк таблицы) определяется как 2N, где N — количество аргументов (т. е. при двух аргументах число строк — 4, при 3 — 8 и так далее).

Законы логики

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

Закон исключенного третьего

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

A ∨ ¬A = 1

Закон непротиворечия

Высказывание не может противоречить самому себе.

A ∧ ¬A = 0

Закон двойного отрицания

Если дважды отрицать высказывание, то получится исходное.

¬¬A = A

Законы повторения (идемпотентности)

Сколько ни повторяй, значение не изменится.

A ∨ A = A                   A ∧ A = A

Законы коммутативности (переместительные)

От перестановки высказываний значение не изменится.

A ∨ B = B ∨ A             A ∧ B = B ∧ A

Законы ассоциативности (сочетательные)

От порядка выполнения операций конъюнкции (дизъюнкции) значение не изменится.

(A ∨ B) ∨ C = A ∨ (B ∨ C)                               (A ∧ B) ∧ C = A ∧ (B ∧ C)

Законы дистрибутивности (распределительные)

A ∨ (B ∧ C) = (A ∨ B)∧(A ∨ C)


A ∧ (B ∨ C) = (A ∧ B)∨(A ∧ C)

Законы поглощения

A ∧ (A ∨ B) = A                      A ∨ (A ∧ B) = A

Законы де Моргана

¬(A∧B) = ¬A ∨ ¬B                 ¬(A∨B) = ¬A ∧ ¬B

Свойства констант

A ∧ 0 = 0         A ∨ 0 = A


A ∧ 1 = A    A ∨ 1 = 1

Доказательства законов логики производятся:

l  с помощью тождественных преобразований выражений;

l  с помощью построения таблиц истинности;

l  с помощью диаграмм Эйлера-Венна.

Источник: https://moodle.kstu.ru/mod/book/view.php?id=21621