загрузка...

ИНФОРМАТИКА И ИКТ ПОДГОТОВКА К ЕГЭ-2013

Глава I. Краткий теоретический справочник

 

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

 

3.7. Построение формул по заданным таблицам истинности

Рассмотрим вначале решение этой задачи на примере. Пусть формула F = F(A1, A2, A3) от трёх высказывательных переменных задана таблицей истинности (см. табл. 1.7).

Таблица 1.7. Таблица истинности формулы от трёх высказывательных переменных.

A1

А2

А3

F(A1, A2, A3)

1

1

1

1

1

1

0

0

1

0

1

1

1

0

0

0

0

1

1

0

0

1

0

0

0

0

1

1

0

0

0

0

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

Помечаем те строки таблицы, в которых F(A1, A2, A3) принимает значение, равное 1. Это строки 1, 3, 7. Для каждой строки (логической возможности) составим формулу, истинную только в этой логической возможности и ложную во всех остальных логических возможностях

1-я строка — А1 ^ А2 ^ А3

3-я строка — А1 ^ ¬ А2 ^ А3

7-я строка — ¬ А1 ^ ¬ А2 ^ А3.

Если возьмём теперь дизъюнкцию всех этих формул, то это и будет искомой формулой:

Рассмотрим другое решение этой задачи. Помечаем те строки таблицы, в которых F(A1, A2, A3) принимает значение, равное 0. Это строки 2, 4, 5, 6, 8. Для каждой логической возможности составим формулу, ложную только в этой логической возможности и истинную во всех остальных логических возможностях

2-я строка — ¬ А1 v ¬ А2 v А3

4-я строка — ¬ А1 v А2 v А3

5-я строка — А1 v ¬ А2 v ¬ А3

6-я строка — А1 v ¬ А2 v А3

8-я строка — А1 v А2 v А3.

Если теперь возьмём конъюнкцию этих формул, то это также будет искомой, то есть имеющей заданную таблицу истинности, формулой:

Формулы (1) и (2) равносильны, так как имеют одну и ту же таблицу истинности. В данном случае удобнее строить формулу (1).





загрузка...
загрузка...