Tudd Intuíció, előadás, logikai függvények és ábrázolások
Kivonat: Az osztály Pn Boole-függvények n-változós. Geometriai ábrázolása logikai funkciókat. Megadása Boole-függvények táblázatok segítségével. Boole-függvények az első és a 2 változó. Boole (logikai) képlet. A problémák megoldását propozicionális logika felhasználásával Boole képletek és függvények
Boole-függvények n változók
Boole-függvények 1. A hazai szakirodalom is gyakran nevezik Boole-függvények. nevezték el a brit matematikus, a tizenkilencedik század, George. Boole, aki először használt algebrai módszerekkel megoldani logikai problémákat. Ők alkotják a legegyszerűbb, nem triviális osztályú diszkrét funkciók - érveiket és értékek esetén csak a két érték (ha több értékeinek erő egyenlő 1, ez egy triviális funkció - állandó!). Másrészt, ez az osztály igen gazdag, és a funkciói sok érdekes tulajdonságokkal. Boole-függvények használnak logika, elektrotechnika, számos területen a számítástechnika.
Legyen B kételemű halmaz. majd
a készlet minden bináris szekvenciák (készlet vektorok) n hosszúságú. Boole-függvény n változók (érvek) bármely olyan f (x1 xn.): B n -> B. Mind a érvek xi. 1 <= i <= n. может принимать одно из двух значений 0 или 1 и значением функции на любом наборе из Bn также может быть 0 или 1. Обозначим через множество всех булевых функций от n переменных. Нетрудно подсчитать их число.
Proof .Indeed által 1.1 Tétel a funkciók száma K -element halmaz a B halmaz m -element m egyenlő k. A mi esetünkben, B =. és A = B n. Akkor m = 2 és k = | B n | = 2 n. Ez magában foglalja a tétel.
Számos különböző módon bemutatása és értelmezése Boole-függvények. Ebben a részben figyelembe vesszük a geometriai és táblázatos bemutatása. és bemutatása logikai képleteket. A „ekvivalencia képletek és a normál formák” jelenik meg, mint egy Boole-függvény lehet képletekkel speciális formája - diszjunktív és konjunktív normál formák és Zhegalkin polinomok. Ezen túlmenően, az előadások „Előzmények” és „indukció és a kombinatorika” (természetesen „Bevezetés a rendszer, gépek és algoritmusok”) figyelembe kell venni, hogy két módon reprezentáló logikai funkciókat. logika és a megrendelt bináris döntési diagramok.
geometriai reprezentáció
Bn lehet tekinteni, mint egy egység n-dimenziós kocka. Minden sor nullák n hosszúságú beállítja a csúcsa a kocka. Ábra. 3.1 egység képviseli Bn kockák n = 3,4.
Ugyanakkor van egy természetes egy-az-egyhez megfelelés közötti egy részhalmaza csúcsainak n-dimenziós egység kockák és Boole-függvények n változók: a részhalmaz megfelel karakterisztikus függvénye
Például, a felső oldala a kocka B 3 (a csúcsait kiosztott az ábrán) megfelel az f függvény. f (0,0,1) = f (0,1,1) = f (1,0,1) = f (1,1,1) = 1 és F (0,0,0) = f (0 , 1,0) = f (1,0,0) = f (1,1,0 részt) = 0. Nyilvánvaló, hogy a fenti megfelelő ténylegesen-on: az egyes f Boole-függvény n készlet változók részhalmazát Af = 1. xn) |. f (x1 xn) = 1> csúcsok B n. Például, függvény azonosan egyenlő 0 meghatároz egy üres halmaz, és függvény azonosan egyenlő 1, meghatározza a készlet minden csúcsok B n.
táblanézet
Boole-függvények egy kis számos érv kényelmesen bemutatott táblázatokkal. Táblázat a f (x1. Xn) van n + 1 oszlopban. Az első N-oszlopokhoz argumentum értékek x1. xn. és (n + 1) -edik oszlop értéke a függvény ezeken érvek - f (x1 xn.).
3.1 táblázat. Táblázatos ábrázolása az f (x1. Xn)