Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: propositional tautology

Sortuj według:

Ogranicz wyniki do:

An algorithm for solving the tautology problem

Karbowska J.

Zeszyty Naukowe Politechniki Białostockiej. Informatyka

2002

Z.1

71-81

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.