Присоединяйтесь к нам в социальных сетях:

Вывод закона поглащения алгебра лгкики

Сложные логические выражения выполняются в следующей последовательности:

1)инверсия;

  1. конъюнкция;

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

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

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

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

Две эквивалентные функции, приравненные друг к другу, называются тождеством.

1.


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

—для дизъюнкции

отрицание дизъюнкции логических переменных эквивалентно конъюнкции отрицаний этих переменных;

—для конъюнкции

отрицание конъюнкции переменных эквивалентно дизъюнкции отрицаний этих переменных.

Справедливость законов отрицания (де Моргана) докажем с помощью таблиц истинности.

Таблица. Закон отрицания (де Моргана) для дизъюнкции

Таблица.Закон отрицания (де Моргана) для конъюнкции

Таблицы 1.5; 1.6 показывают, что на одинаковых наборах переменных значения функций совпадает.
Законы де Моргана доказаны.

5.

По школьным предметам. Подготовка к ЕГЭ

По высшей математике и физике

Онлайн курсы для всех!

Карта сайта Формулы и законы логики

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

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

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

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

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

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

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

Скучно? Нет! – на самом деле очень красиво…. То же самое, кстати, относится к высшей алгебре и некоторым другим предметам.

…но что бы вы прочитали эти строки, я всё-таки преподнёс материал, скорее в «школьном» стиле – с многочисленными содержательными примерами!

Желаю успехов!

Решения и ответы:

Задание 1 Решение: составим таблицу истинности для формулы : (подробные инструкции по заполнению таблицы находятся после условия задачи) Полученный результат совпадает с эквиваленцией высказываний и , таким образом:

Задание 2 Решение: доказательства проведём с помощью таблиц истинности:

а) Дважды записываем все варианты истины и лжи высказывания и применяем к столбцам операцию ИЛИ: Результат совпадает с .

Заодно, кстати, записал вам общую формулу; с точки зрения комбинаторики, здесь размещения с повторениями.

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

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

2) к столбцам применяем правило И;

3) вот теперь выполняем ;

4) и на завершающем шаге применяем импликацию к столбцам и .

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

Задание 3

Выяснить, будет ли являться законом логики следующая формула:

Краткое решение в конце урока.

Инфоinfo
Переместительный (коммутативный) закон

X /\ Y = Y /\ X

X /\ Y = YX /\

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

6. Сочетательный (ассоциативный) закон

(X \/Y) \/Z = X \/ (Y \/Z)

(X/\Y)/\Z=X/\(Y/\Z)

При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

5.


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

(X /\ Y) \/ Z= (X /\ Z) \/ (Y /\ Z)

(X /\ Y) \/ Z = (X \/ Z) /\ (Y \/ Z)

Определяет правило выноса общего высказывания за скобку.

7. Закон общей инверсии Закон де Моргана

¬(X \/ Y) = ¬X /\ ¬Y

¬(X /\ Y) = ¬X \/ ¬Y

Закон общей инверсии.

8.

Тогда высказывание , гласящее о том, что Студент не сдал экзамен, будет равносильно утверждению – Студент не ответил на 1-й вопрос или на 2-й вопрос.

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

Докажем тождество .

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

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

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

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

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

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

В рассуждении: Движение вечно.


Хождение в школу — движение.

Таблица истинности для ИЛИ становится таблицей истинности для И и наоборот.

В этом состоит принцип двойственности, который в общем виде записывается так:

, .

Для любого числа переменных это правило, называемое еще теоремой де Моргана, имеет вид:

.

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

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

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

НЕ запомнить, НЕ распечатать, а именно ещё раз осмыслить и собственноручно переписать на бумагу – чтобы они были перед глазами:

– таблица НЕ; – таблица И; – таблица ИЛИ; – импликационная таблица; – таблица эквиваленции.

Это очень важно. В принципе, их было бы удобно занумеровать «Таблица 1», «Таблица 2» и т.д., но я неоднократно подчёркивал изъян такого подхода – как говорится, в одном источнике таблица окажется первой, а в другом – сто первой.


Поэтому будем использовать «натуральные» названия. Продолжаем:

На самом деле с понятием логической формулы вы уже знакомы.

.

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

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

Задание 1. Установить истинность высказывания . Задание 2 Установить является ли высказывание тавтологией? Задание 3. Установить эквивалентны ли высказывания.

Домашнее задание.

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

;

;

.

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

;

;

.

3.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *