Prove that $(A_1 \land \ldots \land A_n) \to X$ is tautology$ \iff \{A_1, \ldots ,A_n\} \vdash_p X$

104 Views Asked by At

I am having problems with the following exercise:

Prove that the following are equivalent:
$(1)$ $(A_1 \land \ldots \land A_n) \to X$ is tautology
$(2)$ $\{A_1, \ldots ,A_n\} \vdash_p X$

I have the following definitions:
A tautology is a formula $S$ such that for any boolean evaluation $\phi$ it is $\phi(S) = t$.
If $Z$ is a set of formulas then $Z \vdash_p X$ if and only if for all boolean evaluations $\phi$ with $\phi(z) = t$ for all $z \in Z$, $\phi(X) = t$.

I am not sure how to tackle the problem. Any help would be appreciated!

1

There are 1 best solutions below

0
On BEST ANSWER

$(A_1 \land \ldots \land A_n) \to X$ is tautology iff (definition tautology)

for any evaluation $\phi$: $\phi((A_1 \land \ldots \land A_n) \to X)=t$ iff (semantics $\to$)

for any evaluation $\phi$: if $\phi(A_1 \land \ldots \land A_n)=t$, then $\phi(X)=t$ iff (semantics $\land$)

for any evaluation $\phi$: if $\phi(A_i)=t$ for all $1 \le i \le n$, then $\phi(X)=t$ iff (pure logic)

for any evaluation $\phi$: if $\phi(z)=t$ for all $z \in \{A_1, \ldots ,A_n\}$, then $\phi(X)=t$ iff (definition $\vdash_p$)

$\{A_1, \ldots ,A_n\} \vdash_p X$