5.7.4 Loogiset operaatiot

Tehtävä 5.43 de Morganin kaava

Tehtävä 5.44 Osittelulaki

Tehtävä 5.45 Ehtojen sieventäminen

5.7.4 Loogiset operaatiot

Ehtoja usein yhdistellään loogisten operaatioiden avulla:

	Mikäli kello 7- 20 ja et halua ulkoilla
	-  mene bussilla
	...
	Mikäli sinulla on rahaa tai saat kimpan
	-  ota taksi

Yksittäinen ehto antaa tulokseksi tosi ( T=true) tai epätosi ( F=false). Ehtojen tulosta voidaan usein myös kuvata 1 tai 0. Ehtojen yhdistämistä loogisilla operaatioilla kuvaa seuraava totuustaulu (myös C++:n loogiset operaattorit merkitty):

ja

tai

ehd. tai

ei

AND

OR

XOR

NOT

&&

||

 ^ toimii jos p ja q boolean

Huomattakoon edellä, että AND operaatio toimii kuten kertolasku ja OR operaatio kuten yhteenlasku (mikäli määritellään 1+1=1). Siis loogisia operaattoreita voidaan käyttää kuten normaaleja algebrallisia operaattoreita ja niillä operoiminen vastaa tavallista algebraa. Loogisten operaatioiden algebraa nimitetään Boolen - algebraksi.

Ehtojen sieventämisessä käytettäviä kaavoja voidaan todistaa oikeaksi totuustaulujen avulla. Todistetaan esimerkiksi de Morganin kaava (vrt. joukko- oppi, 1=true, 0=false):

	NOT (p AND q) = (NOT p) OR (NOT q)
	
	Jaetaan ensin väittämä pienempiin osiin:
	NOT   e1      =   e2    OR   e3

		e1	e2	e3
p	q	p AND q	NOT p	NOT q	NOT e1	e2 OR e3
0	0	0	1	1	1	1
0	1	0	1	0	1	1
1	0	0	0	1	1	1
1	1	1	0	0	0	0

Koska kaksi viimeistä saraketta ovat samat ja kaikki muuttujien p ja q arvot on käsitelty, on laki todistettu!

Tehtävä 5.43 de Morganin kaava

Todista oikeaksi myös toinen de Morganin kaava:
NOT (p OR q) = (NOT p) AND (NOT q)

Tehtävä 5.44 Osittelulaki

Yhteenlaskun ja kertolaskun välillähän pätee osittelulaki:
: p * (q + r) = (p * q) + (p * r)
Samaistamalla * <=> AND ja + <=> OR todetaan loogisille operaatioillekin osittelulaki:
: p AND (q OR r) = (p AND q) OR (p AND r)
Todista oikeaksi toinen osittelulaki (toimiiko vast. yhteenlaskulla ja kertolaskulla):
: p OR (q AND r) = (p OR q) AND (p OR r)

			e1	e2	e3
p	q	r	q AND r	p OR q	p OR r	p OR e1	e2 AND e3
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1


Huomaa, että totuustauluun tulee nyt 8 riviä (koska kolme muuttujaa)!

Tehtävä 5.45 Ehtojen sieventäminen

Käytä de Morganin kaavoja tai osittelulakia seuraavien ehtojen sieventämiseen:
a): ei ole totta että hinta alle 5 mk ja paino yli 10 kg
b): NOT (kello<=7 OR rahaa>50 mk)
c): ((hinta < 5) tai (rahaa>10)) ja ((hinta < 5) tai (kello>9))