Заключение:

Значит из данных посылок следует .

2.2 Получение логических следствий из данных формул и посылок для данных логических следствий

Логические следствия находят следующим образом:

1) все посылки соединяются конъюнкцией и находятся СКНФ полученной формулы.

2) при выборе любых элементарных дизъюнкций и конъюнкций любых нескольких элементарных дизъюнкций, взятых по два, три и т.д.

получаются все возможные заключения из данных посылок.

Задача 1. Даны посылки: A и AB

Решение:

Логические следствия:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. .

Задача 2. Даны посылки:

Решение:

Логические следствия:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. .

Задача 3. Даны посылки:

Решение:

Логические следствия:

 1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7.

;

Задача 4. Найти формулу F(X, Y), зависящую только от переменных X и Y и являющуюся логическим следствием указанных формул (посылок):

Решение:

Составим таблицу истинности для формул, являющихся посылками:

В правом столбце звездочками отметим те строки, в которых все четыре посылки принимают значение 1. Этому требованию удовлетворяет лишь 15-я строка, в которой ? (X) = 0 и ? (Y) = 0. Следовательно, надо найти такую формулу F (X, Y), для которой F (0, 0) = 1, то такая формула будет логическим следствием четырех данных посылок. Ищем такую формулу, используя СДНФ и считаем, что на всех других наборах значений переменных искомая формула обращается в 0:

F (0, 1) = F (1, 0) = F (1, 1) = 0.

Получаем F (X, Y) .

Задача 5. Найти формулу F(X, Y), зависящую только от переменных X и Y и являющуюся логическим следствием указанных формул (посылок):

Решение:

Составим таблицу истинности для формул, являющихся посылками:

Найдем такую формулу F (X, Y), для которой F (1, 1) = F (0, 1) = F (1, 0) = 1, которая будет логическим следствием двух данных посылок.

F (0, 0) = 0.

Получаем F (X, Y) .

Задача 6. Найти формулу F(X, Y), зависящую только от переменных X и Y и являющуюся логическим следствием указанных формул (посылок):

Решение:

Составим таблицу истинности для формул, являющихся посылками:

Найдем такую формулу F (X, Y), для которой F (0, 0) = 1, которая будет логическим следствием трех данных посылок.

F (1, 0) = F (0, 1) = F (1, 1) = 0.

Получаем F (X, Y) .

Чтобы определить логическим следствием каких посылок является формула А (X₁,X₂,…,X_n), необходимо:

1) привести ее к СКНФ.

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

Найти все не тождественно ложные формулы алгебры высказываний, для которых следующая формула является логическим следствием:

Задача 1.

Решение:

Недостающие дизъюнкции:

Посылка:

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

Задача 2.

Решение:

Недостающие дизъюнкции:

Посылка:

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

Задача 3.

Решение:

Недостающие дизъюнкции:

Посылки:

;

;

;

;

;

;

.

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

Задача 4. Найти недостающую посылку (формулу) F, зависящую лишь от указанных высказываний, чтобы была верна следующая выводимость:

¦

Решение:

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

В правом столбце звездочками отметим те строки, в которых обе данные посылки принимают значение 1, а следствие принимает значение 0. Этому требованию удовлетворяет лишь 12-я строка, в которой ? (Z) = 1 и ? (V) = 1. Ясно, что при этих значениях Z и V искомая посылка F (Z, V) должна принимать значение 0, так как в противном случае формула не будет логическим следствием формул . Будем считать, что на других наборах значений высказываний Z и V формула F (Z, V) принимает значение 1. Итак, для искомой посылки F (Z, V) получаем следующую таблицу истинности:

Находим СКНФ для искомой формулы. Получаем F (Z, V) .

Задача 5. Найти недостающую посылку (формулу) F, зависящую лишь от указанных высказываний, чтобы была верна следующая выводимость:

¦

Решение:

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

В правом столбце звездочками отметим те строки, в которых обе данные посылки принимают значение 1, а следствие принимает значение 0. Этому требованию удовлетворяет лишь 1-я строка, в которой ? (X) = 1 и ? (Y) = 1. Будем считать, что на других наборах значений высказываний X и Y формула F (X, Y) принимает значение 1. Итак, для искомой посылки F (X, Y) получаем следующую таблицу истинности:

Находим СКНФ для искомой формулы. Получаем F (X, Y) .

Задача 5. Найти недостающую посылку (формулу) F, зависящую лишь от указанных высказываний, чтобы была верна следующая выводимость:

¦

Решение:

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

В правом столбце звездочками отметим те строки, в которых обе данные посылки принимают значение 1, а следствие принимает значение 0. Этому требованию удовлетворяет лишь 1-я строка, в которой ? (X) = 1 и ? (Y) = 1. Будем считать, что на других наборах значений высказываний X и Y формула F (X, Y) принимает значение 1. Итак, для искомой посылки F (X, Y) получаем следующую таблицу истинности:

Находим СКНФ для искомой формулы. Получаем F (X, Y) .

Задача 5. Найти недостающую посылку (формулу) F, зависящую лишь от указанных высказываний, чтобы была верна следующая выводимость:

¦

Решение:

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

В правом столбце отметим строку, в которой данная посылка принимает значение 1, а следствие принимает значение 0. Этому требованию удовлетворяет лишь 6-я строка, в которой ? (X) = 0, ? (Y) = 1 и ? (Z) = 0. Будем считать, что на других наборах значений высказываний X, Y, Z формула F (X, Y, Z) принимает значение 1. Итак, для искомой посылки F(X, Y, Z) получаем следующую таблицу истинности:

Находим СКНФ для искомой формулы. Получаем

F (X, Y, Z) .

2.3 Необходимые и достаточные условия

В следующих предложениях вместо многоточия поставьте слова «необходимо, но недостаточно» или «достаточно, но не необходимо», а где возможно «необходимо и достаточно» так, чтобы получилось истинное утверждение:

Задача 1. Пусть на отрезке [a, b] определена непрерывная функция f(x) имеющая на промежутке [a, b] конечные производные, тогда:

Для того, чтобы функция f(x) была постоянной на отрезке [a, b] необходимо и достаточно, чтобы =0 для .

Решение:

F(x)=const на [a, b] - истина

F(x)=const на [a, b] - истина

Задача 2. Для того, чтобы два вектора в пространстве были перпендикулярными, необходимо и достаточно, чтобы их скалярное произведение равнялось нулю

+ - истина

+ - истина

Задача 3. Для того, чтобы уравнение имело действительные корни, необходимо и достаточно, чтобы .

имело действительные корни

имело действительные корни

Задача 4. Для того, чтобы в точке x₀ функция f(x) имела экстремум, необходимо, чтобы

Решение:

функция f(x) в точке x₀ имеет экстремум - истина

функция f(x) в точке x₀ имеет экстремум - ложь

контрпример: .

Задача 5.Для того, чтобы четырехугольник был квадратом, необходимо, но не достаточно, чтобы его диагонали были перпендикулярны.

Решение:

ABCD - квадрат - истина

ABCD - квадрат - ложь

B

контрпример: A C

D

Задача 6.Для того, чтобы уравнение cos x = a имело решение, необходимо, но не достаточно, чтобы .

Решение:

Cos x = a - имеет решение

Cos x = a - имеет решение - ложь

контрпример: a = 3.

Задача 7. Для того, чтобы в точке x₀ функция f(x) имела разрыв второго рода, достаточно, чтобы = ?.

Решение:

функция f(x) в точке x₀ имеет разрыв второго рода - истина.

Задача 8. Для того, чтобы выражение x² - 2x - 3 равнялось нулю, достаточно, но не необходимо, чтобы x = -1.

Решение:

x² - 2x - 3 = 0 - ложь

контрпример: x = 3.

x² - 2x - 3 = 0 - истина

2.4 Анализ и синтез релейно-контактных схем

Одно из применений алгебры высказываний - анализ и синтез релейно-контактных схем.

Еще в 1910 году физик П.С. Эренфест указал на возможность применения аппарата алгебры логики при исследовании релейно-контактных схем. Каждой схеме можно поставить в соответствие некоторую формулу алгебры высказываний, и каждая формула алгебры высказываний реализуется с помощью некоторой схемы.

Рассмотрим 2-х-полюсные переключатели, т.е. такие, которые имеют два состояния: «замкнуто» - 1, «разомкнуто» - 0. На схеме будем изображать:

Определение 7. Переключатель, который сблокирован с X так, что он замкнут, если X разомкнут, и разомкнут, если X замкнут, называется инверсным и обозначается .

Конъюнкция двух высказываний X и Y будет представлена двухполюсной схемой с последовательным соединением двух переключателей X и Y.

Эта схема пропускает ток тогда и только тогда, когда истины и X, и Y одновременно, то есть истина конъюнкция X&Y.

1

X&Y

Дизъюнкция двух высказываний X и Y изобразится двухполюсной схемой с параллельным соединением двух переключателей X и Y.

1

XY

Эта схема пропускает ток в случае, если истинно высказывание X или истинно высказывание Y, то есть истина дизъюнкция XY.

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

Определение 8. Две схемы называются равносильными, если имеют одинаковые функции проводимости.

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

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

Задача 1. Составить РКС, обладающая следующей функцией проводимости:

Решение:

Задача 2. Составить РКС обладающая следующей функцией проводимости:

Решение:

Задача 3. Составить РКС обладающая следующей функцией проводимости:

Решение:

Задача 4. Упростить РКС:

Решение:

Ей соответствует функция проводимости:

F(X,Y,Z)

F(X,Y,Z)

Этой же функции проводимости соответствует более простая схема.

Задача 5. Упростить РКС:

Решение:

Ей соответствует функция проводимости:

Этой же функции проводимости соответствует более простая схема.

Задача 6. Упростить РКС:

Решение:

Ей соответствует функция проводимости:

Задача 7. Какой контакт необходимо вставить в вакантное место, чтобы функция проводимости полученной схемы стала бы равна данной булевой функции:

Данной схеме соответствует функция проводимости:

Решение:

Задача 8. Какой контакт необходимо вставить в вакантное место, чтобы функция проводимости полученной схемы стала бы равна данной булевой функции:

Данной схеме соответствует функция проводимости:

Решение:

Задача 9. Какой контакт необходимо вставить в вакантное место, чтобы функция проводимости полученной схемы стала бы равна данной булевой функции:

Данной схеме соответствует функция проводимости:

Решение:

Задача 10. Построить РКС с четырьмя переключателями, которая проводит ток тогда и только тогда, когда замыкаются не все переключатели, а только некоторые из них.

Решение:

Составим таблицу значений функции проводимости F (X, Y, Z, T) этой схемы:

В правом столбце звездочками отметим те строки, на которых функция F (X, Y, Z, T) обращается в 0, запишем для неё выражение, используя СКНФ, потому что наборов значений аргументов, на которых функция обращается в 0, значительно меньше, чем наборов значений аргументов, на которых функция обращается в 1, и значит, СКНФ будет более простой, чем СДНФ:

Задача 11. Построить схему с тремя переключателями, которая замыкается тогда и только тогда, когда замкнут либо один, либо два переключателя. При построении использовать не более шести контактов.

Решение:

Составим таблицу значений функции проводимости F (X, Y, Z) этой схемы:

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

F (X, Y, Z, T) обращается в 1, запишем для неё выражение, используя СКНФ, потому что наборов значений аргументов, на которых функция обращается в 0, значительно меньше, чем наборов значений аргументов, на которых функция обращается в 1, и значит, СКНФ будет более простой, чем СДНФ:

Задача 12. Требуется составить схему с четырьмя переключателями X, Y, Z, T. Схема должна проводить ток тогда и только тогда, когда будут замкнуты переключатели X и Y или Z и T.

Решение:

Составим таблицу значений функции проводимости F (X, Y, Z, T) этой схемы:

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

F (X, Y, Z, T) обращается в 1, запишем для неё выражение, используя СДНФ:

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

Работа РКС описывается функцией Буля трех переменных F (X, Y, Z), где переменные высказывания X, Y, Z означают:

X - судья X голосует «за»

Y - судья Y голосует «за»

Z - судья Z голосует «за»

Таблица истинности функции F (X, Y, Z) имеет вид:

Этой же функции проводимости соответствует более простая схема.