- •1.8. Анализ и синтез релейных управляющих схем
- •1.8.1. Релейные схемы. Связь их физической структуры и функций проводимости с алгеброй логики
- •1.8.2. Проектирование рс
- •1.9. Применение алгебры логики к анализу логических рассуждений
- •1.10. Замкнутость и полнота систем функций
- •1.10.1. Операции суперпозиции и замыкания. Полнота, базис системы функций
- •1.10.2 Функции, сохраняющие константы. Классы т0 и т1
- •1.10.3. Самодвойственность. Класс s
- •1.10.4. Монотонность. Класс м
- •1.10.5. Линейность. Класс l
- •1.10.6. Критерий Поста полноты системы функций в алгебре логики
- •Контрольные задания по теме
- •Операция суперпозиции.
- •Замыкание и полнота систем функций.
- •Предполные классы в алгебре логики
- •1.11. Анализ и синтез функциональных схем
- •Пример 1. В качестве фэ приняты { , , }. Произвести анализ фс, физическая структура которой дана на рис.1.19.
- •10. Оптимизировать фс из фэ { , , }, приведеную на рис.1.25.
- •Контрольные задания по теме применение алгебры логики к анализу и синтезу релейных и функциональных схем, проверке правильности высказываний
1.9. Применение алгебры логики к анализу логических рассуждений
Предметом изучения логики является сам процесс построения логического вывода рассуждений, безотносительно к содержательному смыслу исходных высказываний.
Логика рассуждений зачастую бывает достаточно сложной. Для анализа ее правильности любое рассуждение должно быть представлено в формализованном виде.
Определение. Пусть Р1 ,Р2 ,..., Рk — некоторые исходные высказывания, которые могут быть как простыми, так и составными. Их называют посылками. На основании одновременной истинности посылок делается вывод о справедливости некоторого нового высказывания V, который называют заключением.
Если вывод делается только в одну сторону, от посылок к заключению (прямая посылка), то данное действие описывается при помощи логической связки “импликация” (). Если же верна и обратная посылка от V к Р1 ,Р2 ,..., Рk, то их соединяют связкой «эквивалентность» (). Это следует из тавтологии: (ху) (ху) & (ух) .
Определение. Получаемую формулу вида F = (Р1 Р2 … Рk) V (либо F=(Р1 Р2 .. Рk ) V) называют формулой логического заключения .
Очевидно, каждое конкретное рассуждение является частным случаем применения некоторой общей логической формулы. Рассмотрим примеры рассуждений и построим соответствующие им формулы логических заключений.
Пример 1. Пусть А, В, C — некоторые элементарные высказывания. Относительно них сформулировано следующее рассуждение: «если из справедливости А следует В, а из B следует C, то из А следует С».
Обозначив Р1 = А В, Р2 = В С, V = А C, получим формулу заключения вида: F = (А В) (В С)(АC).
Пример 2. Высказано следующее рассуждение: «Если некоторая задача решена верно, то ответ будет правильный. Следовательно, из правильности ответа следует верность решения задачи».
Рассмотрим элементарные высказывания: А = «Задача решена верно», В = « Получен правильный ответ». Введя составные высказывания — посылку Р1 = А В и заключение V = В А, получим формулу вывода F = (А В) (В А).
Определение. Логический вывод называют правильным, если соответствующая ему формула логического заключения является тавтологией.
Рассмотрим формулу заключения из примера 1. Проверим ее тавтологичность путем построения таблицы истинности соответствующей функции. После поэтапного ее построения получим, что F = (А В) (В С)(АC) 1.
A |
B |
C |
Р1 =А В |
Р2 =ВС |
Р1Р2 |
V=АC |
F=Р1Р2 V |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Ответ: F — тавтология, поскольку реализующая ее функция тождественно равна 1. Рассуждения, основанные на ней, являются всегда правильным.
Проверим правильность формулы заключения из примера 2 путем построения векторов истинности посылки, заключения и итоговой функции, соответствующей F.
A |
B |
Р1 = А В |
V = В А |
F = Р1 V |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
F не является тавтологией, поэтому соответствующий ей логический вывод может давать неверные результаты. Например, посылка Р1 может быть равна 1 (если задача решена верно, то ответ всегда правилен), однако заключение V может быть неверным (правильный ответ может быть получен путем неверного решения). Поэтому при Р1 = 1 и V = 0 рассуждение будет неверно. Это соответствует ситуации, когда решение “подогнано под ответ”. Таким образом, использование неправильного логического вывода привело к тому, что в некоторых ситуациях неверно и конкретное рассуждение, основанное на нем.
Замечание. Правильность рассуждения в каком-либо конкретном случае не является достаточным условием правильности примененного в нем логического вывода. В частности, в Примере 2 можно рассмотреть ситуацию, когда Р1= 1 и V=1. Тогда F = Р1 V = 1, т.е. в данном случае рассуждение верно. Однако, если формула заключения F не является тавтологией, то всегда можно указать случаи, когда F = 0 и рассуждение не верно.
При всем многообразии рассуждений их формулы заключений, отражающие логику, обычно сводятся к нескольким наиболее распространенным видам. Рассмотрим их.
Основные виды тавтологий, применяемых в логических рассуждениях
1. А (А В) В. Правило сокращения посылки «модус поненс»: « если верно А и из А следует В, то верно и В».
2. В (А В) А. - Опровержение посылки. «Если В неверно и из А следует В, то неверно и А».
3. ((А1 А2 ... Аn) В) (А1 В) (А2 В) ... (Аn В). Доказательство путем разбора частных случаев.
4. Схемы доказательств «от противного».
а) А ( А ( В В)). «Правильность некоторого утверждения А можно доказать, показав, что из его отрицания следует одновременно справедливость некоторого утверждения В и его отрицания»,
б) (А В) (( А В) А). Противоречие по посылке. Пусть теорема утверждает, что из А следует В. Если допустить, что А верно, а В не верно, то отсюда можно доказать ложность А — посылки теоремы (т.о. одновременно истинны А и А ),
в) (А В) (( А В) В). Противоречие по заключению. Если допустить, что А верно, а В не верно, то можно доказать истинность В —заключения теоремы. В итоге получаем одновременную истинность В и В.
ЗАДАЧИ
1. Доказать справедливость тавтологии: (х у) (ху) & (ух).
2. Доказать справедливость стандартных формул логических заключений, приведенных в пп.1-4.
3. Проверить правильность рассуждения: «Если событие А произошло и оно происходит при наличия условий В , то условия В также выполнены».
4. Предприятию требуется один сотрудник без вредных привычек. Первый кандидат сказал о себе следующее: «Я курю, только когда выпью, но курить бросил». Второй кандидат сообщил: «Я тоже курю, только когда выпью, но бросил пить». С помощью формул логических заключений выяснить, кто из кандидатов должен быть принят на работу.