Tautologia w rachunku predykatów
: 29 paź 2023, o 20:43
Mam takie zadanie
Udowodnij ,że wyrażenie jest tautologią
\(\displaystyle{ [\bigwedge\limits_{x} \phi(x) \Rightarrow \Psi ] \Rightarrow \bigvee\limits_{x} [\phi(x) \Rightarrow \Psi]}\)
gdzie \(\displaystyle{ \Psi}\) jest funkcja zdaniowa ktora nie zawiera x jako zmiennej wolnej.
Próbowałem to udowodnić w ten sposób
Jedynym wartościowaniem dla którego \(\displaystyle{ [\bigwedge\limits_{x} \phi(x) \Rightarrow \Psi ] \Rightarrow \bigvee\limits_{x} [\phi(x) \Rightarrow \Psi] \equiv 0}\) to gdy zachodzi
\(\displaystyle{ [\bigwedge\limits_{x} \phi(x) \Rightarrow \Psi ] \equiv 1}\)
\(\displaystyle{ \bigvee\limits_{x} [\phi(x) \Rightarrow \Psi] \equiv 0}\)
Pierwsze zdanie można rozumieć ,że dla dowolnego \(\displaystyle{ x}\) \(\displaystyle{ \phi(x)}\) ma własność \(\displaystyle{ \Psi}\)
Z kolei drugie czytam jako istnieje \(\displaystyle{ x}\) taki że \(\displaystyle{ \phi(x)}\) nie ma własności \(\displaystyle{ \Psi}\), a to stoi w sprzeczności z poprzednim zdaniem, zatem nigdy wyjściowe zdanie nie będzie dawało 0 więc musi być zawsze prawdziwe. Czy taki dowód "słowny" jest akceptowalny i czy w ogóle jest on prawidłowy? Czy istnieje jakiś bardziej formalny dowód tego że formuła jest tautologią?
Udowodnij ,że wyrażenie jest tautologią
\(\displaystyle{ [\bigwedge\limits_{x} \phi(x) \Rightarrow \Psi ] \Rightarrow \bigvee\limits_{x} [\phi(x) \Rightarrow \Psi]}\)
gdzie \(\displaystyle{ \Psi}\) jest funkcja zdaniowa ktora nie zawiera x jako zmiennej wolnej.
Próbowałem to udowodnić w ten sposób
Jedynym wartościowaniem dla którego \(\displaystyle{ [\bigwedge\limits_{x} \phi(x) \Rightarrow \Psi ] \Rightarrow \bigvee\limits_{x} [\phi(x) \Rightarrow \Psi] \equiv 0}\) to gdy zachodzi
\(\displaystyle{ [\bigwedge\limits_{x} \phi(x) \Rightarrow \Psi ] \equiv 1}\)
\(\displaystyle{ \bigvee\limits_{x} [\phi(x) \Rightarrow \Psi] \equiv 0}\)
Pierwsze zdanie można rozumieć ,że dla dowolnego \(\displaystyle{ x}\) \(\displaystyle{ \phi(x)}\) ma własność \(\displaystyle{ \Psi}\)
Z kolei drugie czytam jako istnieje \(\displaystyle{ x}\) taki że \(\displaystyle{ \phi(x)}\) nie ma własności \(\displaystyle{ \Psi}\), a to stoi w sprzeczności z poprzednim zdaniem, zatem nigdy wyjściowe zdanie nie będzie dawało 0 więc musi być zawsze prawdziwe. Czy taki dowód "słowny" jest akceptowalny i czy w ogóle jest on prawidłowy? Czy istnieje jakiś bardziej formalny dowód tego że formuła jest tautologią?