In the present paper we propose an algorithm deciding, whether a given formula a is a tautology of the propositional logic. The worst case complexity of the algorithm is of the order .
W pracy został przedstawiony algorytm sprawdzania czy dana formuła rachunku zdań należąca do języka , zbudowana ze zmiennych, stałej zero, nawiasów oraz znaku implikacji, jest tautologią. Idea algorytmu jest oparta na regułach transformacji. Reguły te zachowują tautologiczność formuły, tzn. formuła , która jest tautologią po zastosowaniu odpowiedniej reguły w dalszym ciągu jest tautologią. Jeśli dana formuła jest różna od stałej lub zmiennej, to w formule znajdujemy ostanie wystąpienie znaku implikacji i stosujemy odpowiednią regułę otrzymując nowy ciąg formuł. Formuły przekształcamy do momentu, kiedy otrzymamy ciąg pusty (wtedy jest ona tautologią), bądź zmienną bądź stałą. Złożoność tego algorytmu, w najgorszym przypadku, wynosi , gdzie oznacza długość formuły.
Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies
Informacja
SZANOWNI CZYTELNICY!
UPRZEJMIE INFORMUJEMY, ŻE BIBLIOTEKA FUNKCJONUJE W NASTĘPUJĄCYCH GODZINACH:
Wypożyczalnia i Czytelnia Główna: poniedziałek – piątek od 9.00 do 19.00