Решение

Выделим простые высказывания и запишем их через переменные:
– «ветра нет»; – «пасмурно»; – «дождь».

Запишем логические функции (сложные высказывания) через введенные переменные:

§ если не будет ветра, то будет пасмурная погода без дождя: ;

§ если будет дождь, то будет пасмурно и без ветра: ;

§ если будет пасмурная погода, то будет дождь и не будет ветра: .

Запишем произведение указанных функций:

 

.

 

Упростим формулу (используются законы де Моргана, переместительный закон, закон противоречия):

 

 

 

 

Приравняем результат к единице, т. е. наше выражение должно быть истинным: .

Проанализируем результат.

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

Ответ: погода будет ясная, без дождя, но ветреная.

 

2.3.2. Решение логических задач табличным способом

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

Пример 3. В симфонический оркестр приняли на работу трёх музыкантов: Брауна, Смита и Вессона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе.

Известно, что:

§ Смит самый высокий;

§ играющий на скрипке меньше ростом играющего на флейте;

§ играющие на скрипке и флейте и Браун любят пиццу;

§ когда между альтистом и трубачом возникает ссора, Смит мирит их;

§ Браун не умеет играть ни на трубе, ни на гобое.

На каких инструментах играет каждый из музыкантов, если каждый владеет двумя инструментами?

Решение

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

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

Из условия 4 следует, что Смит не играет ни на альте, ни на трубе, а из условий 3 и 5, что Браун не умеет играть на скрипке, флейте, трубе и гобое. Следовательно, инструменты Брауна – альт и кларнет.

Занесем это в таблицу, а оставшиеся клетки столбцов «альт» и «кларнет» заполним нулями:

 

Музыкант	Скрипка	Флейта	Альт	Кларнет	Гобой	Труба
Браун
Смит
Вессон

 

Из таблицы видно, что на трубе может играть только Вессон.

Из условий 1 и 2 следует, что Смит не скрипач. Так как на скрипке не играет ни Браун, ни Смит, то скрипачом является Вессон. Оба инструмента, на которых играет Вессон, теперь определены, поэтому остальные клетки строки «Вессон» можно заполнить нулями:

 

Музыкант	Скрипка	Флейта	Альт	Кларнет	Гобой	Труба
Браун
Смит
Вессон

 

Из таблицы видно, что играть на флейте и на гобое может только Смит.

 

Музыкант	Скрипка	Флейта	Альт	Кларнет	Гобой	Труба
Браун
Смит
Вессон

Ответ: Браун играет на альте и кларнете, Смит – на флейте и гобое, Вессон – на скрипке и трубе.

 

2.3.3. Решение логических задач с помощью рассуждений

Способом с помощью рассуждений обычно решают несложные логичес­кие задачи.

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

Решение

Имеется три утверждения:

– Вадим изучает китайский;

– Сергей не изучает китайский;

– Михаил не изучает арабский.

Если верно первое утверждение, то верно и второе, так как юноши изучают разные языки. Это противоречит условию задачи, поэтому первое утверждение ложно.

Если верно второе утверждение, то первое и третье должны быть ложны. При этом получается, что никто не изучает китайский. Это противоречит условию, поэтому второе утверждение тоже ложно.

Остается считать верным третье утверждение, а первое и второе – ложными. Следовательно, Вадим не изучает китайский, китайский изучает Сергей.

Ответ: Сергей изучает китайский язык, Михаил – японский, Вадим – арабский.

 

2.4. Булевы функции. Свойства элементарных булевых функций

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

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

Перечисленные операции подчиняются следующим законам.

Коммутативные законы: , .

Ассоциативные законы:

, .

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

, .

Законы идемпотентности: , .

Закон двойного отрицания: .

Законы де Моргана: , .

Законы поглощения: , .

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

Алгебра логики и алгебра множеств – булевы алгебры.

Булева функция, или функция алгебры логики, является одним из основных объектов дискретной математики.

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

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

Определение 2.Две булевы функции называются равными, если для любых одинаковых наборов значений переменных обе функции принимают одинаковые значения. Булевых функций одной переменной четыре, а двух переменных – шестнадцать и т. д. Число булевых функций от переменных равно .

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

Составим таблицы истинности таких функций.

Таблица истинности булевой функции одной переменной:

 

 

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

Таблица истинности булевой функции двух переменных:

 

константа 0

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

импликация

| штрих Шеффера

константа 1

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

1.Функции и представляют собой константы 0 и 1.

2.Функции , , , существенно зависят только от одной переменной: , , , .

3.Остальные функции существенно зависят от двух переменных, и для них есть названия и обозначения:

а) функция называется конъюнкцией;

б) функция называется дизъюнкцией;

в) функция называется эквивалентностью;

г) функция называется суммой по модулю два, или суммой Жегалкина;

д) функция называется конверсией;

е) функция называется импликацией;

ж) функция называется штрихом Шеффера;

и) функция называется стрелкой Пирса;

к) функции и логически несовместимы с импликацией и конверсией и называются функциями запрета.

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

1. Функции: конъюнкция, дизъюнкция, сумма по модулю два, стрелка Пирса, штрих Шеффера обладают свойством коммутативности.

2. Функции: конъюнкция, дизъюнкция, сумма по модулю два обладают свойством ассоциативности и свойством дистрибутивности.

3. Закон де Моргана: ; .

4. Закон двойного отрицания: .

5. Выражение дизъюнкции через конъюнкцию и суммы по модулю два: .

6. Выражение дизъюнкции через импликацию: .

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

8. Выражение конъюнкции через штрих Шеффера:

.

9. Выражение дизъюнкции через стрелку Пирса:

.

10. Закон поглощения: ; .

11. Закон склеивания: .

12. Для функций конъюнкции, дизъюнкции и сумме по модулю два справедливы следующие тождества:

 

; ; ; ;

; ; ; ;

; ; ; .

 

13. Для функций конъюнкции и дизъюнкции справедливы тождества: ; .

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

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

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

2.5. Дизъюнктивные и конъюнктивные нормальные
формы булевых функций

Определение 1.Конъюнктивным одночленом (элементарной конъюнкцией) от переменных называется конъюнкция этих переменных или их отрицаний.

Например, – элементарная конъюнкция.

Определение 2.Дизъюнктивным одночленом (элементарной дизъюнкцией) от переменных называется дизъюнкция этих переменных или их отрицаний.

Например, – элементарная дизъюнкция.

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

Например, – ДНФ.

Определение 4.Формула, равносильная данной формуле алгебры высказываний и являющаяся конъюнкцией элементарных дизъюнктивных одночленов, называется конъюнктивной нормальной формой (КНФ) данной формулы.

Например, – КНФ.

Для каждой формулы алгебры высказываний можно найти множество дизъюнктивных и конъюнктивных нормальных форм.