Графический способ решения системы логических уравнений.

Проанализировав 12 ветвей дерева можно сделать вывод, что ответом является 1 или 2 ветвь графического дерева.

Алгоритм.

алг Задача № 16 (цел A1, A2, A3, B1, B2, C1, F1, F2, F3, F4, F5,
F6, F7, F8, F9, F10, F11, F12, F13, F )
арг A1, A2, A3, B1, B2, C1, F1, F2, F3, F4, F5, F6, F7, F8,
F9, F10, F11, F12, F13
рез F
нач
A1:=0
20:A2:=0
30:A3:=0
40:B1:=0
50:B2:=0
60:C1:=0
70:F1:=(A1 И НЕ C1) ИЛИ (НЕ A1 И С1)
F2:=(НЕ A2) ИЛИ B1
F3:=(B2 И НЕ A2) ИЛИ (НЕ B2 И A2)
F4:=(HЕ A3) ИЛИ(НЕ C1)
F5:=НЕ(A1 И A2)
F6:=НЕ(A1 И A3)
F7:=НЕ(A2 И A3)
F8:=НЕ(A2 И B2)
F9:=НЕ(B1 И B2)
F10:=НЕ(A1 И B1)
F11:=НЕ(A1 И B1)
F12:=НЕ(С1 И B1)
F13:=A1 ИЛИ A2 ИЛИ A3
F:=F1 И F2 И F3 И F4 И F5 И F6 И F7 И F8 И F9 И F10
И F11 И F12 И F13
если F=1
то вывод F, A1, A2, A3, B1, B2, C1
все
если C1<1
то C1:=1: переход к 70
все
если B2<1
то B2:=1: переход к 60
все
если B1<1
то B1:=1: переход к 50
все
если A3<1
то A3:=1: переход к 40
все
если A2<1
то A2:=1: переход к 30
все
если A1<1
то A1:=1: переход к 20
все
кон

Бейсик - программа.

1 cls
10 A1=0
20 A2=0
30 A3=0
40 B1=0
50 B2=0
60 C1=0
70 f1=(a1 and not c1) or (not a1 and c1)
80 f2=(not a2) or b1
90 f3=(b2 and not a2) or (not b2 and a2)
100 f4=(not a3) or (not c1)
110 f5=not(a1 and a2)
120 f6=not(a1 and a3)
130 f7=not(a2 and a3)
140 f8=not(a2 and b2)
141 f9=not(b1 and b2)
142 f10=not(a1 and b1)
143 f11=not(a1 and c1)
144 f12=not(c1 and b1)
145 f13=a1 or a2 or a3
150 f=f1 and f2 and f3 and f4 and f5 and f6 and f7 and f8 and f9 and f10 and f11 and f12 and f13
160 if f=1 then?" f ";"a1 ";"a2 ";"a3 ";"b1 ";"b2 ";"c1 ":?f ;a1 ;a2 ;a3 ;b1 ;b2 ;c1
170 if c1<1 then c1=1:goto 70
180 if b2<1 then b2=1:goto 60
190 if b1<1 then b1=1:goto 50
200 if a3<1 then a3=1:goto 40
210 if a2<1 then a2=1:goto 30
220 if a1<1 then a1=1:goto 20
230 end

Паскаль - программа.

program zad2;
uses crt;
var a1,a2,a3,b1,b2,c1:boolean;
function func{(a1,a2,a3,b1,b2,c1)}:boolean;
var f:array[1..13] of boolean;
begin
f[1]:=(a1 and not c1) or (not a1 and c1);
f[2]:=(not a2) or b1;
f[3]:=(b2 and not a2) or (not b2 and a2);
f[4]:=(not a3) or (not c1);
f[5]:=not(a1 and a2);
f[6]:=not(a1 and a3);
f[7]:=not(a2 and a3);
f[8]:=not(a2 and b2);
f[9]:=not(b1 and b2);
f[10]:=not(a1 and b1);
f[11]:=not(a1 and c1);
f[12]:=not(c1 and b1);
f[13]:=a1 or a2 or a3;
func:=f[1] and f[2] and f[3] and f[4] and f[5] and f[6] and f[7] and f[8] and f[9] and f[10] and f[11] and f[12] and f[13];
end;
procedure ff(i:integer);
begin
case i of
1:begin
a1:=false;ff(i+1);
a1:=true;ff(i+1);
end;
2:begin
a2:=false;ff(i+1);
a2:=true;ff(i+1);
end;
3:begin
a3:=false;ff(i+1);
a3:=true;ff(i+1);
end;
4:begin
b1:=false;ff(i+1);
b1:=true;ff(i+1);
end;
5:begin
b2:=false;ff(i+1);
b2:=true;ff(i+1);
end;
6:begin
c1:=false;ff(i+1);
c1:=true;ff(i+1);
end;
7:begin
if func{(a1,a2,a3,b1,b2,c1)}=true then
begin
writeln('a1 a2 a3 b1 b2 c1');
writeln(a1,' ',a2,' ',a3,' ',b1,' ',b2,' ',c1);
end;
end;
end;
end;
begin
ff(1);
end.

Задача №3.

Нужно для 4 дежурных - Антипова, Климова, Маркова и Лебедева - составить график дежурств на агитпункте с соблюдением следующих условий:

Если Лебедев не будет дежурить в понедельник, то в понедельник
согласен дежурить Климов.
Ecли Климов не сможет дежурить ни в понедельник, ни в четверг, то Антипов будет дежурить в понедельник.
Если Марков не сможет дежурить в четверг, то Климов будет дежурить в среду.
Если Лебедев придет дежурить во вторник ,то Климов не будет
дежурить в понедельник .
Если Антипов не сможет дежурить в понедельник, то Марков не
сможет дежурить во вторник.

Каким должен быть график дежурств ?

Решение. Введем обозначения: L- Лебедев, K - Климов, A - Антипов, M - Марков. Цифры означают 1 - Понедельник,2 - Вторник,3 - Среда, 4 -Четверг.
Согласно условиям задачи составим систему логических уравнений:

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

L2 * L1= 0 (6)
К1* L1= 0 (7)
К1* А1= 0 (8)
К4* M4= 0 (9)
L1*А1= 0 (10)

Для решения системы уравнений умножим сначала уравнение (1)
на уравнение (2):

Ответ.Из полученного выражения следует, что Климов дежурит в понедельник, Антипов - во Вторник, Лебедев - в среду, Марков - в Четверг.

Алгоритм.

алг Задача 12 (цел F1, F2, F3, F4, F5, F6, F7, F8, F9, Fa, Fb, F,
K1, K3, K4, L2, L1, M4, A1)
арг F1, F2, F3, F4, F5, F6, F7, F8, F9, Fa, Fb
рез F, K1, K3, K4, L2, L1, M4, A1
нач
15: М2:=0
20: К1:=0
30: К3:=0
40: К4:=0
50: L2:=0
60: L1:=0
70: M4:=0
80: A1:=0
90: F1:=( L1 или К1 )
F2:=( K1 или К4 ) или А1
F3:=( M4 или К3 )
F4:=( не L2) или не К1
F5:=( A1 или не М2 )
F6:=( не ( К1 и К3 )) и ( не (К3 и К4)) и (не (К1 и К4))
F7:= не ( L2 и L1)
F8:= не ( К1 и L1 )
F9:= не ( К1 и А1 )
Fa:= не ( К4 и М4 )
Fb:= не ( L1 и А1)
F:=F1 и F2 и F3 и F4 и F5 и F6 и F7 и F8 и F9 и Fa и Fb
если F=1
то вывод F, K1, K3, K4, L2, L1, M4, A1
все
если А1>1
то А1:=1: перейти к 90
все
если М4<1
то М4:=1: перейти к 80
все
если L1<1
то L1:=1: перейти к 70
все
если L2<1
то L2:=1: перейти к 60
все
если К4<1
то К4:=1: перейти к 50
все
если К3<1
то К3:=1: перейти к 40
все
если К1<1
то К1:=1: перейти к 30
все
если М2<1
то М2:=1: перейти к 20
все
кон

Бейсик-программа.

10 CLS
20 K1=0
30 K3=0
40 K4=0
50 L2=0
60 L1=0
70 M4=0
80 A1=0
90 F1=(l1 OR K1 )
100 F2=( K1 or K4) or A1
110 F3=(m4 OR K3)
120 F4=( NOT l2) OR not K1
130 F5=(a1 or not m2)
140 f6=(not(k1 and k3)) and (not(k3 and k4)) and (not(k1 and k4))
150 F7= NOT(L2 AND L1)
160 F8= NOT(K1 AND L1)
170 F9= NOT(K1 AND A1)
180 Fa= NOT(K4 AND M4)
190 Fb= NOT(L1 AND A1)
200 F=F1 AND F2 ANd F3 AND F4 AND F5 AND f6 and F7 AND F8 AND F9 AND fa and fb
210 IF F=1 THEN ?" F ";"K1 ";"K3 ";"K4 ";"L2 ";"L1 ";"M4 ";"A1 ":?F;K1;K3;K4;L2;L1;M4;A1
220 IF A1<1 THEN A1=1:GOTO 90
230 IF M4<1 THEN M4=1:GOTO 80
240 IF L1<1 THEN L1=1:GOTO 70
250 IF L2<1 THEN L2=1:GOTO 60
260 IF K4<1 THEN K4=1:GOTO 50
270 IF K3<1 THEN K3=1:GOTO 40
280 IF K1<1 THEN K1=1:GOTO 30
290 END

Паскаль-программа.

PROGRAM zad3;
uses crt;
var M2,K1,K3,K4,L2,L1,M4,A1:boolean;
function func:boolean;
var f:array[1..11] of boolean;
begin
f[1]:=(L1 OR K1); f[2]:=(K1 or K4)OR A1; f[3]:=(M4 OR K3);
f[4]:=(not L2) or (not K1); f[5]:=(a1 OR NOT M2);
f[6]:=not(K1 and K3) AND (NOT(K3 AND K4)) AND (NOT(K1 AND K4));
f[7]:=not(L2 and L1); f[8]:=not(K1 and L1); f[9]:=not(K1 and A1);
f[10]:=not(K4 and M4); f[11]:=not(L1 and A1);
func:=f[1] and f[2] and f[3] and f[4] and f[5] and f[6] and f[7] and f[8] and f[9] and f[10] and f[11] ; end;
procedure ff(i:integer);
begin
case i of
1:begin M2:=false;ff(i+1); M2:=true;ff(i+1); end;
2:begin K1:=false;ff(i+1); K1:=true;ff(i+1); end;
3:begin K3:=false;ff(i+1); K3:=true;ff(i+1); end;
4:begin K4:=false;ff(i+1); K4:=true;ff(i+1); end;
5:begin L2:=false;ff(i+1); L2:=true;ff(i+1); end;
6:begin L1:=false;ff(i+1); L1:=true;ff(i+1); end;
7:begin M4:=false;ff(i+1); M4:=true;ff(i+1); end;
8:begin A1:=false;ff(i+1); A1:=true;ff(i+1); end;
9:begin
if func=true then
begin
writeln('K1 K3 K4 L2 L1 M4 A1');
writeln(K1,' ',K3,' ',K4,' ',L2,' ',L1,' ',M4,' ',A1);
end;
end;
end;
end;
begin
CLRSCR;
ff(1);
end.

Задача №4.

Обсуждая вопрос о включении в состав сборной команды пяти молодых игроков : Асеева, Валеева, Сватеева, Деева и Евтеева.

Выбор обусловлен следующими условиями:

В команду необходимо включить не менее чем одного из трех игроков: Асеева, Валеева, Евтеева, но не более чем одного из трех игроков: Асеева, Сватеева, Деева.
Сватеева можно включить в сборную без Валеева тогда и только тогда, когда Асеев будет включен, а Деев не будет включен.
Если Валеев будет включен в сборную, а Сватеев не будет включен, то сборную нужно пополнять и Деевым, и Евтеевым.
Если Асеев не будет включен в команду, то нужно в нее включить и Сватеева, и Евтеева.

Кого из игроков можно включить в сборную команду?

Решение.Введем буквенные обозначения: A-Асеев, E-Евтеев, B-Валеев, D-Деев, C-Сватеев. Условия выбора игроков для сборной команды заданы в задаче высказываниями 1,2,3,4. По этим высказываниям выпишем формулы:

Для решения системы логических уравнений сначала умножим уравнение (2) на уравнение (3):

Умножим полученное выражение (6) на уравнение (4), получим:

Умножим полученное выражение (7) на уравнение (1), получим:

В уравнении (8) перемножим сначала выражение, заключенное в первые скобки, на выражение, заключенное в третьи скобки, получим:

Перемножим полученное выражение (9) на выражение, заключенное в вторые скобки, уравнения (8), получим:

Ответ.В команду включены: Валеев, Сватеев, Евтеев.

Алгоритм.

алг задача (цел a,e,b,d,q,w,r,f1,f2,f3,f4,f)
арг a,e,b,d,q,w,r,f1,f2,f3,f4
рез f
нач
1: a:=0
2: e:=0
3: b:=0
4: d:=0
5: c:=0
6: q:=(a и не e и не b) или (не a и не e и b) или (не a и e и не b)
w:=(a и e и не b) или (a и не e и b) или (не a и b и e) или (a и e и b)
r:=(a и не c и не d или не a и c и не d или не a и не c и d)
f1:=(q или w) и r
f2:=((c и не b) и (a и не d)) или (не(c и не b) и не(a и не d))
f3:=не(b и не c) или (d и e)
f4:=a или (c и e)
f:=f1 и f2 и f3 и f4
если f=1
то вывод a;e;b;d;c
все
если c<1
то c:=1: переход на 6
все
если d<1
то d:=1: переход на 5
все
если b<1
то b:=1: переход на 4
все
если e<1
то e:=1: переход на 3
все
если a<1
то a:=1: переход на 2
все
кон

Бейсик-программа.

cls
10 a=0
20 e=0
30 b=0
40 d=0
50 c=0
60 q=(a and not e and not b)or(not a and not e and b)or(not a and e and not b)
w=(a and e and not b)or(a and not e and b)or(not a and b and e)or(a and e and b)
r=(a and not c and not d or not a and c and not d or not a and not c and d)
f1=(q or w) and r
f2=((c and not b) and (a and not d))or(not(c and not b) and not(a and not d))
f3=not(b and not c) or (d and e)
f4=a or (c and e)
f=f1 and f2 and f3 and f4
if f=1 then ?" A ";"E ";"B ";"Д ";"C ":? a;e;b;d;c
if f=1 then stop
if c<1 then c=1:goto 60
if d<1 then d=1:goto 50
if b<1 then b=1:goto 40
if e<1 then e=1:goto 30
if a<1 then a=1:goto 20
end

Паскаль-программа.

program zad4;
uses crt;
var c,e,b,a,d:boolean;
function func{(a1,a2,a3,b1,b2,c1)}:boolean;
var f:array[1..7] of boolean;
begin
f[1]:=(a and e and not b)or(not a and not e and b)or(not a and e and not b);
f[2]:=(a and e and not b)or(a and not e and b)or(not a and b and e)or(a and e and );
f[3]:=(a and not c and not d or not a and c and not d or not a and not c and d);
f[4]:=(f[1] or f[2]) and f[3];
f[5]:=((c and not b)and(a and not d))or(not(c and not b) and not(a and not d));
f[6]:=not(b and not c) or (d and e);
f[7]:=a or (c and e);
func:=f[4] and f[5] and f[6] and f[7];
end;
procedure ff(i:integer);
begin
case i of
1:begin
a:=false;ff(i+1); a:=true;ff(i+1);
end;
2:begin
e:=false;ff(i+1); e:=true;ff(i+1);
end;
3:begin
b:=false;ff(i+1); b:=true;ff(i+1);
end;
4:begin
d:=false;ff(i+1); d:=true;ff(i+1);
end;
5:begin
c:=false;ff(i+1); c:=true;ff(i+1);
end;
6:begin
if func=true then begin writeln('a e b d c');
writeln(a,' ',e,' ',b,' ',d,' ',c); end;
end; end; end;
begin
clrscr; ff(1);
8:end.

Задача.

Три грибника, рассматривая найденный гриб, высказали свои предположения. Первый грибник сказал: "Не верно, что, если это не опенок, то этот гриб съедобный". Второй грибник также был осторожен и сказал: "Не верно, что этот гриб или ядовитый, или опенок, или не сыроежка". Третий грибник заявил: "Это гриб не ядовитый, и я отрицаю, что если это сыроежка, то она съедобна". В итоге оказалось, что все три грибника были правы и их суждения оказались истинными. Какой гриб нашли грибники?
Решение.
A="Гриб опенок"
B="Гриб сыроежка"
C="Гриб съедобный"
D="Гриб ядовитый"

Так как высказывания всех трех грибников истинны, то итоговая функция равна их конъюнкции:

Функция импликации преобразуется в дизъюнктивную нормальную форму следующим образом:

Функция F принимает единичное значение только на одном наборе значений аргументов, в котором a=0, b=1,c=0, d=0, т.е. найденный гриб - сыроежка.

Бейсик-программа.

REM Задача о грибниках
CLS
PRINT " "; "A"; " "; "B"; " "; "C"; " "; "D"; " "; "F"
FOR A = 0 TO 1
FOR B = 0 TO 1
FOR C = 0 TO 1
FOR D = 0 TO 1
F1 = NOT (NOT A IMP C)
F2 = NOT (D OR A OR NOT B)
F3 = NOT D AND NOT (B IMP C)
F = F1 AND F2 AND F3
PRINT A; B; C; D; F
NEXT D, C, B, A
END

Паскаль-программа

PROGRAM GRIB;
USES CRT;
VAR A,B,C,D,F1,F2,F3,F:INTEGER;
BEGIN
CLRSCR;
WRITELN ('A','B','C','D','F');
FOR A:=0 TO 1 DO
FOR B:=0 TO 1 DO
FOR C:=0 TO 1 DO
FOR D:=0 TO 1 DO
BEGIN
F1:=NOT(A) AND NOT(C);
F2:=NOT (A) AND B AND NOT (D);
F3:=NOT (D) AND B AND NOT (C);
F:=F1 AND F2 AND F3;
WRITELN (A,B,C,D,F);
END;
END.

⇐ Назад

Далее ⇒