|
Способов решения несколько, предпочитаю такой:
Упрощаем выражение
¬A → (¬P ˄ ¬Q)
A ˅ ¬P ˄ ¬Q
Рассмотрим все варианты начал и окончаний цепочек:
00ххххх0
00ххххх1
01ххххх0
01ххххх1
10ххххх0
10ххххх1
11ххххх0
11ххххх1
Оставшиеся иксы принимают одно из двух значений, то есть на каждую строку приходится 2^5=32 разных цепочек:
00ххххх0 - 32
00ххххх1 - 32
01ххххх0 - 32
01ххххх1 - 32
10ххххх0 - 32
10ххххх1 - 32
11ххххх0 - 32
11ххххх1 - 32
Выражение должно быть истинно для любого x. То есть, если для каких-либо цепочек выражение ¬P ˄ ¬Q ложно, значит эти цепочки обязательно должны входить в множество А. Рассмотрим истинность выражения ¬P ˄ ¬Q для каждой строки, учитывая, что P начинается с 11, а Q заканчивается нулем:
00ххххх0 - ¬P ˄ ¬Q = ¬0 ˄ ¬1 = 0
00ххххх1 - ¬P ˄ ¬Q = ¬0 ˄ ¬0 = 1
01ххххх0 - ¬P ˄ ¬Q = ¬0 ˄ ¬1 = 0
01ххххх1 - ¬P ˄ ¬Q = ¬0 ˄ ¬0 = 1
10ххххх0 - ¬P ˄ ¬Q = ¬0 ˄ ¬1 = 0
10ххххх1 - ¬P ˄ ¬Q = ¬0 ˄ ¬0 = 1
11ххххх0 - ¬P ˄ ¬Q = ¬1 ˄ ¬1 = 0
11ххххх1 - ¬P ˄ ¬Q = ¬1 ˄ ¬0 = 0
Получается, что в пяти случаях выражение ¬P ˄ ¬Q ложно, значит эти цепочки должны входить в множество А.
На каждую строку приходится 32 цепочки, значит минимальное количество цепочек в множестве А = 32*5=160
| 
