Kombinatorik och boolesk algebra - Hur många booleska funktioner finns som uppfyller villkoret....
Hej!
Jag undrar om hur man löser denna fråga:
Hur många booleska funktioner f(x,y,z) med 3 variabler x,y,z finns som uppfyller villkoret att:
f(0,0,1) + f(0,0,0)+ f(1,1,1) f(1,0,1)? (boolesk addition gäller)
Lösning:
I boolesk algebra antar funktioner bara värdet 0 och 1.
Så först kan vi ju tänka att om högerledet:
f(1,0,1) = 0, då måste alla funktioner i vänsterledet vara = 0, f(0,0,1) = 0, f(0,0,0) = 0 och f(1,1,1) = 0:
0 + 0 + 0 ≤ 0
Om högerledet är:
f(1,0,1) = 1, så kan vi uppfylla olikheten genom att växla värdet på f(0,0,1), f(0,0,0) och f(1,1,1) och se till att minst en av de är 1.
Hur kan jag räkna antalet funktioner som uppfyller villkoret i så fall?
Enligt facit kommer svaret bli funktioner. Hur fås detta?
Med 3 variabler har vi totalt 23 = 8 inputkombinationer.
Om f(1,0,1)=0, måste vi ha 0 för f(0,0,1), f(0,0,0), och f(1,1,1). Men alla andra (4) kombinationer kan resultera vilken output som helst (0 eller 1). Det innebär 24 = 16 funktioner.
Om f(1,0,1)=1, uppfyller alla tänkbara funktioner villkoret. Alla inputkombinationer förutom (1,0,1) kan resultera 0 eller 1. Det innebär 27 = 128 funktioner.
f(1,0,1) = 1, så kan vi uppfylla olikheten genom att växla värdet på f(0,0,1), f(0,0,0) och f(1,1,1) och se till att minst en av de är 1.
Nej, de kan också vara 0.
Tack för svaret!! Nu förstår jag det här, tack!
