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

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

Получаем СКНФ. Пример 1. Постройте КНФ функции

.

Решение Исключим связку «

» с помощью законов преобразования переменных: = законы де Моргана и двойного отрицания/ =

/дистрибутивные законы/ =

. Пример 2. Приведите к ДНФ формулу

. Решение Выразим логические операции

и

через

,

и

:

Доказательство таблицы истинности дистрибутивного закона

Операнды и результаты некоторых побитовых операций X У х & у X v у X IMP y .x EQV y х XOR y Логические операции.

NOT. Поразрядный оператор not (he), или дополнение, является одноместной операцией, которая выполняет логическое отрицание на каждом бите, формируя дополнение данного би­нарного значения. Биты, содержавшие бывшие «0», устанавлива­ются в «1»; и наоборот.

Этот оператор не следует путать с «логическим отрицанием» («!» — восклицательный знак), который обрабатывает все значение как отдельное булевское.

Билет № 11. Дизъюнкция высказываний и её свойства (доказательство одного из них)

Отрицание высказываний и его свойства (доказательство одного из них). Билет № 13. Импликация высказываний и её свойства (доказательство одного из них).

Обратная, противоположная и обратная противоположной импликации.

Импликацией двух высказываний A и B называется новое высказывание A=>B(из А следует В, если А то В),которое ложно только в том случаи, когда А-ИСТИНА,В-ложь, во всех остальных случаях! Импликация-истина А В A=>B И И И И Л Л Л И И Л Л И Свойства: 1.

закон контропозиции A=>B ó В =>A A B A=>B В A В => A И И И Л Л И И Л Л И Л Л Л И И Л И И Л Л И И И И Если дана импликация A=>B ,то импликация В=>A называется обратной A=>B противоположной данной В =>A обратно — противоположной данной.

Эквиваленция высказывания — …двух высказ. a и b,называется новое высказывание AB,которые

Свойства операций над высказываниями

5.

;

;

; 6.

(или

) (закон исключенного третьего);

(или

(закон противоречия); 7.

(или

);

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

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

В рассуждении: Движение вечно. Хождение в школу — движение.

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

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

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

Формулы и законы логики

Поэтому будем использовать «натуральные» названия. Приведу стандартное, но довольно-таки остроумное определение: формулами алгебры высказываний называются: 1) любые элементарные (простые) высказывания

; 2) если

и

– формулы, то формулами также являются выражения вида

.

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

. Поскольку

–

Дистрибутивности закон

и A / (B & С) экв.

к. из высказывания

«для всякого x справедливо свойство Φ или свойство Ψ»

не следует высказывание «для всякого x справедливо свойство Φ или для всякого x справедливо свойство Ψ», хотя обратное следование и имеет место).

Операция же связывания переменной квантором существования дистрибутивна относительно дизъюнкции: (т.е. высказывания «существует такое x, для к-рого верно Φ или Ψ» и «существует такое x, для к-рого верно Ф, или существует

Тавтологии логики предикатов

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

Пусть

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

Получим формулу логики предикатов: .

Если теперь вместо предикатных переменных подставить произвольные конкретные предикаты , то формула превратится в конкретный предикат .

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

Свойства операций конъюнкции и дизъюнкции

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

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

Сформулируем предложения, выражаемые этими формулами. Р = «Любое действительное число больше 0 или меньше 1».

Q =

«Любое действительное число больше 0 или любое действительное число меньше 1»

. Предложение Р истинно, так как всякое действительное число попадет в интервал (-оо; 1) или (0; +оо), поскольку их объединение даст все множество R Предложение Q ложно, так как оба высказывания УдгеН(д>0) и VagR(xложны.

Действительно, существование отрицательного числа х=- опровергает первое утверждение, а существование числа х=2 опровергает второе утверждение. Итак, предложения Р и Q не равносильны.

• Этот пример показывает, что формулы V.* (А(хУ/В(х)) и /дЛ(д)у/д?(д) (в общем случае) не равносильны.

zakondostatka.ru

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

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

не содержит переменную

, то используем равносильность

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

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

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

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

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

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

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

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

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

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

А=А

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

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

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

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

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

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

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

• В начало

  • Страницы сайта

    • Теги

    • Календарь

    • Новости сайта

  • Курсы

    • Дистанционные курсы

    • Школьные площадки

      • Волжский район

      • Заводской район

      • Кировский район

      • Ленинский район

      • Октябрьский район

      • Фрунзенский район

      • ОУ городского подчинения и ГБУ

      • Саратовская область

      • СОИРО

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

    • О портале

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

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

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

    • Семинары

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

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

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

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

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

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

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

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