Файл: Алгебра высказываний.doc

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 17.03.2019

Просмотров: 2125

Скачиваний: 5

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Практика по алгебре высказываний











Практика

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

КРАТКАЯ ТЕОРИЯ


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

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

Примеры высказываний: «Один полюс один равняется двум»; «Москва – столица Германии»; «Идет дождь, а у меня нет зонта».

Приведенные примеры показывают, что высказываниями могут быть как простые предложения («Один полюс один равняется двум»; «Москва столица Германии»), так и сложные («Идет дождь, а у меня нет зонта»). Простые высказывания не содержат в своем составе других высказываний («Биология является предметом, изучаемым в школе»), а сложные – состоят из нескольких простых («Математика и физика относятся к естественным наукам»: «Математика – естественная наука», «Физика – естественная наука»).

Для обозначения простых высказываний используют большие латинские буквы A, B, …, а для их значений – 1 (истина) и 0 (ложь). Переменные A, B, … в этом смысле часто называют пропозиционными переменными (propositio – предложение-высказывание).

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

Таблица 1



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

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

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

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

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

A

B

A&B

AB

AB

BА

AB

1

1

1

1

1

1

0

1

1

0

0

1

0

1

0

0

0

1

0

1

1

0

1

0

0

0

0

0

1

1

1

1


Пример 1. Определите значение сложного логического выражения , если известно, что А=В =1, С=0.

Решение

Имеем: А=1, В=1, С=0. Подставим эти значения в формулу и произведем вычисления:

.

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


При вычислении значений логических выражений следует помнить о порядке приоритетности операций, он следующий: 1) инверсия, 2) конъ­юнкция; 3) дизъюнкция; 4) импликация и эквивалентность. Для изменения порядка действий, используются скобки.

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

Таблица 2

Форма высказывания
естественного языка

Соответствующая формула языка
алгебры логики

Не А;

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

А не имеет места

А и В;

как А, так и В;

не только А, но и В;

А вместе с В;

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

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

АВ

А, но не В;

не В, а А

А или В;

А, или В, или оба;

А либо В;

А, разве что В

Либо А, либо В;

не А, разве что не В;

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

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

Либо А, либо В и С;

А, разве что В и С

Либо А и В, либо С и D

Если А, то В;

В, если А;

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

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

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

А только при условии что В;

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

А, значит В;

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

А влечет В;

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

все А есть В;

из А следует В;

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

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

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

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

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

АВ


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

Решение. Сначала выделим и обозначим простые высказывания:

  1. А= «Урок будет интересным»

  2. Р= «Петя пойдет в кино».

  3. В= «Ваня пойдет в кино».

  4. К= «Коля пойдет в кино».

Тогда

  1. = «Петя не пойдет в кино».

  2. = «Ваня не пойдет в кино».

  3. = «Коля не пойдет в кино».

Отсюда

= «Никто из мальчиков – Петя, Ваня, Коля – не пойдет в кино».

И, наконец,

= «Если урок будет интересным, никто из мальчиков – Петя, Ваня, Коля – не пойдет в кино».


Символы 0 и 1 можно рассматривать как логические константы, а обозначения простых высказываний – латинские буквы A, B, C, … – как имена логических переменных. Тогда логической формулой (функцией) называется выражение, составленное по определенным правилам из логических переменных (пропозициональных высказываний), логических связок и скобок, позволяющее наглядно описать форму строения составных высказываний. Дадим теперь точное определение формулы:

  1. Пропозициональная переменная является формулой.

  2. Если А формула, то тоже формула.

  3. Если A и B формулы, то (AB), (AB), (AB) тоже формулы.

  4. Никаких других формул нет.


Пример 3. Проверить является ли формулой следующее выражение .

Решение. A, B, C и D – пропозициональные переменные, следовательно (по п.1 определения формулы), они являются формулами. Тогда: 1) , – формулы 2) – формула 3) – формула 4)  – формула.


Формула называется тождественно истинной, если при всех значениях входящих в нее переменных высказываний она принимает значение истина. Примеры тождественно истинных формул: , .

Формулу называется выполнимой, если она принимает значение «истина» при некоторых значениях входящих в нее переменных высказываний. Примеры выполнимых высказываний: , .

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


Пример 4. Доказать выполнимость формулы . Выписать значения переменных, при которых формула принимает: а) истинные значения; б) ложные значения.

Решения

Для доказательства построим таблицу истинности.

Номер
комбинации

А

В

С

1

1

1

1

1

0

0

1

2

1

1

0

1

1

1

1

3

1

0

1

1

0

0

1

4

1

0

0

1

1

1

1

5

0

1

1

1

0

0

1

6

0

1

0

1

1

1

0

7

0

0

1

0

0

0

1

8

0

0

0

0

1

0

1


Из таблицы видно, что существуют такие комбинации значений входящих переменных, при которых формула принимает истинное значение, например при A=1, B=1, C=1, следовательно, формула выполнима.

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

Номер
комбинации

А

В

С

1

1

1

1

2

1

1

0

3

1

0

1

4

1

0

0

5

0

1

1

7

0

0

1

8

0

0

0

а ложна только при одной комбинации:

Номер
комбинации

А

В

С

6

0

1

0


Алгоритм построения таблицы истинности:

1. Определение количества столбцов таблицы

Количество столбцов

=

Количество
логических
переменных

+

Количество
логических операций
формулы

2. Определение количества строк таблицы

Количество строк

=

2n, где n – количество логических операций формулы

3. Заполнение заголовка таблицы

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

4. Заполнение строк таблицы

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

Две формулы и называются равносильными (=), если при любых значениях , где – совокупность всех переменных, входящих в и , эти формулы принимают одинаковые значения. Например, равносильно , равносильно . В табл. 3 приведены основные равносильности алгебры логики.

Таблица 3

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

A=A

(1)

закон тождества

(2)

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

(3)

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

(4)

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

(5)

(5*)

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

(6)

(6*)

законы коммутативности

(7)

(7*)

законы ассоциативности

(8)

(8*)

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

(9)

(9*)

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

(10)

(10*)

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

К этому списку можно добавить свойства логических констант:

(11)

(11*)

отрицание лжи

отрицание истины

(12)

(12*)

прибавление логической константы 0

прибавление логической константы 1

(13)

(13*)

умножение на логическую константу 0

умножение на логическую константу 1

AB=

(14)


=

(15)


=

(16)


=

(17)


=

(18)



Пример 5. Проверьте, будет ли верна следующая равносильность

Решение. Используя таблицу 3, получим:


Будем говорить, что операция & двойственная операции и наоборот.

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

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

Пример 6. Найти формулу двойственную формуле .

Смотрите также файлы