ЧАСТЬ 1. ТЕОРИЯ.

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

№

Операция

Обозначение

Истолкование

Таблица истинности

1

Инверсия

(логическое отрицание)

не А; В;

не А;

неверно, что А

А

В

0

1

1

0

2

Конъюнкция

(логическое произведение)

AB;

AЛB;

A и B

А и В;

как А, так и В;

А вместе с В;

А несмотря на В;

А, в то время как В

А

В

AЛB

0

0

0

0

1

0

1

0

0

1

1

1

3

Дизъюнкция не строгая

(логическое сложение)

A+B;

AVB;

A или B

А или В;

А или В или оба.

А

В

AVB

0

0

0

0

1

1

1

0

1

1

1

1

4

Дизъюнкция строгая

(исключающая ИЛИ)

либо А, либо Б;

А или В, но не оба

А

В

0

0

0

0

1

1

1

0

1

1

1

0

5

Импликация

(логическое следование)

A→B;

Если А, то В;

В если А;

В необходимо для А;

А достаточно для В;

В тогда, когда А

А

В

A→B

0

0

1

0

1

1

1

0

0

1

1

1

6

Эквиваленция

(равнозначность)

A= B;

A↔B;

A~B

А эквивалентно В;

А необходимо и достаточно для В;

А тогда и только тогда, когда В;

А если и только если В

А

В

A↔B

0

0

1

0

1

0

1

0

0

1

1

1

7

Стремлка Пимрса

A ↓ B

ни A, ни B

А

В

A ↓ B

0

0

1

0

1

0

1

0

0

1

1

0

8

Штрих Шемффера

X|Y

Не А или не В

А

В

X|Y

0

0

1

0

1

1

1

0

1

1

1

0

Приоритет логических операций:

НЕ нашли? Не то? Что вы ищете?

действия в скобках; инверсия; конъюнкция; дизъюнкция; импликация; эквиваленция.(стрелки со штрихами точно ненай)

Формулы:

1) Рефлексивность ()

2) Симметричность (Если , то )

3) Транзитивность ()

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

1) - тождествия

2) - противоречия

3) - исключенного третьего

4) - двойного отрицания

5) - идемпотентности

6) - коммутативности

7) - ассоциативности

8) - дистрибутивности

9) - де Моргана

10)

11) - поглощения

12) - склеивания

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

x↓y ≡ (x∧ y) ≡ (xVy)

x|y ≡ (xV y) ≡ (x∧y)

ЧАСТЬ 2. ПО СУЩЕСТВУ.

1. Построить СДНФ и СКНФ функции…

ДНФ - сумма элементарных произведений. Пример:

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

КНФ – произведение элементарных сумм. Пример:

СКНФ(соверш. коньюкт. норм. форма) – произведение совершенных сумм. Пример: . (отличие от КНФ так же в том, что нужно писать все переменные xyz)

Способы построения:

-Табличный;

-Эквивалентные преобразования.

1) Табличный.

-упростить

-построить таблицу истинности

-Пишем СДНФ и СКНФ по правилам:

СДНФ строится по строчкам, где функция равна единице, если переменная 0, то с отрицанием, если 1 – без отрицания;

СКНФ строится по строчкам, где функция равна нулю, если переменная 0, то с отрицанием, если 1 – без отрицания;

Пример:

x

y

z

F

0

0

0

1

0

0

1

1

0

1

1

0

0

1

0

0

1

0

1

0

1

0

0

1

1

1

1

0

1

1

0

1

СДФН:

СКНФ:

2) Эквивалентные преобразования.

Пример:

Продолжим преобразования предыдущего примера

СДНФ получаем, путем домножения на отсутствующие элементы и раскрывания скобок():

СКНФ получаем, путем многократного применения закона дистрибутивности ():

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

2. Написать формулу по фразе…

Задание:

-выписать атомарные функции

-составить формулу по фразе

-составить отрицание к данной формуле

-записать составленную отрицательную формулу человеческим языком

Как делать: ознакомится с истолкованиями операций в таблице на первой странице. Ну смотреть примеры и скрестить пальцы…

Примеры:

14.2) Юристы знают математику лучше, чем логику.

23.2) Если Москва – большой город, то Солнце заходит на западе.

3. Определить тип формулы (выполнима, тождественно истинна, тождественно ложна)

Тождественно истинна – значит формула всегда выдает 1 и ее можно приравнять к 1.

Тождественно ложна – значит формула всегда выдает 0 и ее можно приравнять к 0.

Выполнима – может выдавать как 1 так и 0, в зависимости от входных параметров.

Как проверить:

а) построить таблицу истинности и посмотреть результаты

б) равносильные преобразования. Использовать различные формулы для приведения формулы к 0 или 1, если это возможно.

Пример:

4.Привести формулу к виду -формулы(квантор общьности).

F -> ПНФ(пренексная нормальная форма) -> -формула

ПНФ – формула вида Q1…QnF, где Q-кванторы(), а F формула. Тоесть формула приведена к виду, где кванторы перенесены из формулы и стоят слева.

-формула – формула не содержащая квантеров существования()

Алгоритм:

Пусть нам дана ()

1) к ПНФ:

-избавится от импликации(→) и эквивалентности(~) ()

-пронести знак ⌐ внутрь формулы (вобщем упростить, причем и наоборот) ()

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

-вынести вперед все кванторы, причем порядок их должен оставатся таким же, как они встречаются в формуле ().

2) к -формуле:

-избавится от кванторов , путем замены вхождения ее переменных на новые функции зависящие от всех переменных квантеров , предшествующих ее вхождению (), если перед ним нет квантеров , то ее вхождения заменить на константу(например C)

Пример1:

       -ПНФ

       --формула

Пример2:

               -ПНФ

       --формула

Пример3:

       -ПНФ

       --формула