Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 8
Текст из файла (страница 8)
Существует простой способ найти высказывание, которому она соответствует. Например, предположим, что имеется таблица истинности Случай р гг 1 Т Т 2 Т т' 3 т Т 4 т' Р' Т Т Т Известно, что р Ло истинно в случае 1 и ложно во всех остальных случаях. Аналогично, р л д истинно только в случае 2, рлдн истинно только в случае 3, а р Л д истинно только в случае 4.
Пусть высказывание должно быть истинным точно в указанных нами случаях. Если для каждого такого случая (строки таблицы) выбрать высказывание, которое истинно только в этом случае, и связать эти высказывания связкой Ч, то мы получим высказывание, истинное только в требуемых случаях (строках). В приведенном выше примере рассматриваемая таблица истинности соответствует высказыванию (рлдн) н(р л-д) ь (-р л-4). В случае таблиц истинности с тремя переменными имеем аналогичную ситуацию.
Для каждой строки следующей таблицы приведено высказывание, истинное только для этой строки. Случай р г1 т Заметьте, что если в какой-либо строке переменная имеет ложное значение, то в соответствующем высказывании она использована с отрицанием. Если требуется построить высказывание, соответствующее конкретной таблице истинности, 1 Т Т Т 2 Т Т т' 3 Т т' Т 4 Т Р т' 5 т' Т Т 6 т' Т т 7 т' т' Т 8 т' т' Р рлсЛт рЛ зЛ-т рЛ сЛт р Л-д Л-т -рЛ4Лт рЛдЛ т рЛ сЛт -р Л-д Л-т РЯЗДЕЛ 1.5. Полнота а логике высказываний 47 необходимо выбрать выражения, соответствующие случаям (строкам), где выска- зывание истинно, и соединить их связкой Ч, Например, построение высказывания с таблицей истинности Случай р а г дает высказывание (рЛдЛг) Ч(рЛд Л г)Ч( рЛг1Лг) Ч( р Л а Л г).
Построение высказывания с таблицей Случай р ц г дает высказывание (рЛд Л г)Ч(р Л дЛг)Ч( рЛо Л г). Такая форма выражения высказывания называется дизъюнктивной нормальной формой. Выражения рло Л г, р Л-олг и рло Л г называются элементарными конъюнкциями. Дадим более точное определение, ОПРЕДЕПЕНИЕ 1.5. Пусть р1, рз, рз, ..., р„— простые высказывания. Назовем выражение х1 Л хз Л хз Л Л х„, в котором х, = р; или х; = р„ элементарной конъюнкцией. Выражение, представляюшее собой дизъюнкцию элементарных конъюнкций, называется диэъюнктивной нормальной формой, так что если ты тз, тз, ..., т„есть элементарные конъюнкции, тогда т, Ч тз Ч тз Ч . Ч т„ЕСтЬ ДИЗЪЮНКтИВНаЯ НОРМаЛЬНаЯ фОРМа. Т Т Т Т Т г Т Г Т Т г г г Т Т г Т Г е Р Т Г г Г Т Т Т Т Т г Т Г Т Т г г г Т Т Г Т Г г г Т г Г Г Т Т р Г Т Г г Т р Т Т г г Т г Г 48 ГЛАВА 1.
Таблицы истинности, логика, доказательства Хотя любое высказывание может быть выражено в дизъюнктивной нормальной форме, эта форма высказывания не является простейшей. Карты Карно, которым посвящен следующий раздел, как раз позволяют упростить выражение высказывания в дизъюнктивной нормальной форме. Действуя по той же схеме, мы замечаем, что рЧ д Ч т ложно, только когда р, д и т ложны. Вообще, в таблице Случай р ц т рЧ цЧ 1 р Ч г1Чт рыдЧ т рЧдЧт рЧ цЧ т р Ч-1Чт рЧоЧ т рЧдЧт каждое выражение ложно в строке, где оно расположено, и истинно в любой другой строке. Если требуется найти высказывание, обладающее данной таблицей истинности, зная все случаи (строки), где в таблице истинности стоит ложное значение, то используются высказывания, каждое из которых ложно только в соответствующей строке, и все эти высказывания объединяются связкой л.
Например, таблице истинности вида Случай р с7 т 1 Т Т Т 2 Т Т г 3 Т г Т 4 Т г г 5 г' Т Т 6 г Т г' 7 г г Т 8 г г г соответствует высказывание ( рЧд Ч т)Л( рЧг1Чт)Л(рЧ г7Чт)Л(рЧдЧ т). Такая форма выражения высказывания называется конъюнктивной нормальной формой. Выражения рЧд Ч т, рЧг1Чт, р Ч-г1Чт и рЧггЧ т носят название элементарных диэъюнкций. Теперь дадим более формальное определение. ОПРЕДЕЛЕНИЕ 1.8. Пусть ры рз, рз, ..., р„— простые высказывания.
Назовем выражение х1ЧхзЧхзЧ...Чх„,в котором х; =р, или р,, элементарной диэъюнкцией. 1 2 3 4 6 7 8 Т Т Т Т Т г Т г Т Т г Г г Т Т г Т Г г г Т Т Т г г Т г р Т РлэдЕЛ 1.6. Полнота а лоаина аыоказыааний 49 ° УПРАЖНЕНИЯ 1. Используя таблицы истинности, докажите, а) р 1 р эквивалентно р; б) (р ) р) ) (д 1 о) эквивалентно р л о; в) (Р ) Ч) 1 (р ) д) эквивалентно (р 4 д), 2. Найдите высказывания, которым отвечают что следующие таблицы истинности: а) Случай р д т б) Случай р <7 т 1 Т Т Т 2 Т Т т 3 Т Г Т 4 Т Г т 5 Г Т Т 6 Р Т т' 7 т' Г Т 1 Т Т Т 2 Т Т т' 3 Т т' Т 4 Т Г Г 5 т' Т Т 6 т' Т т 7 т' т' Т 8 Г т т в) Случай р ц т 3.
Найдите высказывания, кот а) Случай р д т следующие таблицы ист Случай р д т орым отвечают инности: б) 1 Т Т Т 2 Т Т т' 3 Т т Т 4 Т т' Г 5 Г Т Т 6 т' Т Г 7 т т Т 8 Г Г т' 1 2 3 4 6 7 8 Т Т Т Т Т т' Т т' Т Т Г Г Г Т Т т Т т' т т' Т т т т Т Т т' Т Г Т Т Т Т р Г Г Т т Т Т Т р т т Т 1 2 3 4 5 6 7 8 Т Т Т Т Т т' Т Г Т Т т Г Г Т Т т Т Г Р Г Т т Г Т т' Т Г Г Т т' Т Г К К Т Т т Т 50 ГЛАВА я Таблицы истинности, логика, доказательства в) Случай р о г 1.6. КАРТЫ КАРНО Для простых высказываний р,, рз, рз, ... и р„существует 2" различных элементарных конъюнкций. (Это будет показано в главе 8.) Например, для высказываний р и о элементарными конъюнкциями будут рлу, р л о, рлд и р л д.
Карта Карно — это таблица, каждый элемент которой является элементарной коньюнкцией. Например, для высказываний р и о карта Карно должна иметь вид, изображенный на рис. 1.1, а на рис. !.2 внутри прямоугольников представлены соответствующие элементарные конъюнкции. Рис. 1.1 Рис. 1.2 Для представления картой Карно высказывания, записанного в дизъюнктивной нормальной форме, необходимо поместить х в прямоугольниках, соответствующих элементарным конъюнкциям. Например, высказыванию (рло) ч(-р л-д) соответствует карта Карно, изображенная на рис. 1.3.
я о Рис. 1.3 Рис. 1.4 Заметим, что если высказыванию соответствует карта Карно с двумя соседствующими в строке или в столбце х, тогда выражение можно упростить, сведя Т Т Т Т Т с Т с' Т Т с Е с Т Т Е Т Е Е Е Т с р' с Т Е Т Т Е Е Т с' РАЗДЕЛ 7.б. Карты Карно 61 две элементарные конъюнкции к одной, содержащей на одну компоненту меньше (т.е. либо р, либо о не будут присутствовать в выражении).
Например, высказывание (р л о) и'(р л о), которому соответствует карта Карно, изображенная на рис. 1.4, эквивалентно высказыванию р, так как (р Лг7)ч (р л д) = рЛ (д'и Ч) †= рл Т— : р. г -г г Рис. Дб Карта Карно для р, о и г может иметь вид, изображенный на рис. 1.5, а на рис. !.6 в прямоугольниках внутри представлены элементарные конъюнкции. Рис. Дб Следовательно, высказыванию (р л о л -г) ч (р л -д л г) ч (-р л о л -г) будет соответствовать карта Карно, изображенная на рис.
1.7. г -г г Рис. Д7 Как и прежде, поскольку два знака соседствуют, две элементарные коньюнкции могут быть сведены к одной, содержащей на одну из компонент р, о и г меньше. В данном случае (рло л г) и( рли л г) сводится к (о л-г), так что выражение принимает вид (7 Л-г) и(р Л-д Л г). В случае, когда четыре значка расположены в прямоугольнике рядом, как показано на рис. 1.8 г Рис. Дб 52 ГЛАВА 1. Таблицы истинности, логика, доказательства или на рис. 1.9, г -г г Рис. 1.9 тогда четыре элементарные конъюнкции, отмеченные значками, могут быть сведены к одному члену, содержащему только одну из компонент р, о и т. Например, первая карта Карно представляет (рло л-т) ч(р л-олт) ч (-рло л-т) ч(-р л-о л-т), что сводится к т.
Вторая карта Карно представляет выражение 1рлолт)ч грло л-т)ч 1р л-д л-т)ч(р л-олт), что может быть сведено к р. Поскольку т появляется на обоих концах карты Карно, ее можно "скрутить" и считать, что четыре значка на карте Карно образуют прямоугольник из четырех значков (см. рис. 1.10), поэтому выражение (р л д л т) ч (-р л д л т) ч 1р л -о л т) ч (-р л -о л т) сводится просто к т.
г Рис. 1.10 Выражение 1р Л о Л т) Ч ( р Л о Л т) Ч (р Л о Л т) Ч ( р Л о Л т) Ч (р Л о Л т), представленное на рис. 1.11, может быть преобразовано к дч(р л о л т) на основе правостороннего блока из четырех значков. Более того, благодаря наличию блока из двух значков в середине первой строки, его можно еще больше упростить, приведя к виду с1Ч (р Л т).
г Рис. 1.П РАЭДЕП 1.б. Карты Карно 53 Перечислим четыре последовательных шага при использовании карты Карно; 1. Для каждой элементарной конъюнкции обозначьте на карте соответствую- щий прямоугольник. 2. Покройте знаки, используя, по возможности, несколько прямоугольных бло- ков.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
