Логикалық байланыстардың толық жүйелері туралы қазақша реферат

Логикалық байланыстардың толық жүйелері

D1, D2, …, Dn — логикалық амалдардың символдары болсын. Егер тұжырымдар алгебрасының кез келген формуласы үшін соған пара-пар, яғни логикалық жағынан тең мәнді, және тек D1, D2, …, Dn амалдарының көмегімен құрылған формула табылатын болса, онда <D1, D2, …, Dn> жиыны толық жүйе деп аталады.

Негізгі тұжырым

Тұжырымдар алгебрасының кез келген формуласы үшін соған пара-пар ДНФ (дизъюнктивті нормаль форма) және КНФ (конъюнктивті нормаль форма) бар болғандықтан, <Ø, Ù, Ú> жүйесінің толық екендігі түсінікті.

Леммалар

Лемма 9.1

Логикалық байланыстардың келесі жиындары толық жүйе құрайды:

<Ø, Ù, Ú, ®>
<Ø, Ù>
<Ø, Ú>
<Ø, ®>

Лемма 9.2

Келесі жиындар логикалық амалдардың толық жүйесін құрмайды:

<Ù, Ú, ®>
<Ø>

Қысқаша қорытынды

Толық жүйе ұғымы — берілген логикалық амалдар жиынының тұжырымдар алгебрасындағы кез келген формуланы логикалық тең мәнді түрде өрнектеуге жеткіліктілігін сипаттайды. Осы тұрғыдан алғанда, кейбір жиындар барлық формулаларды құруға жеткілікті болса, кейбіреулері мұндай мүмкіндікті қамтамасыз етпейді.