Mathematical logic

Question

Given:

1. $[(A \lor B) \land (A \lor C)] \rightarrow [A \lor (B \land C)]$;

2. $\lnot((x_1 < x_2) \rightarrow (x_1 \cdot x_3 > x_2 \cdot x_3))$

3. $\forall x_2:f_1^2(x_2, x_3) \rightarrow P_1^2(f_1^1(x_1), f_1^3(x_1, a_2, x_1))$;

The tasks are:

Q1. To derive (1) in the propositional calculus.

Q2. To give examples of 3 interpretations: Tautology, Contradiction, Satisfiable (but not tautological) of (2).

Q3. Is (3) a formula?

---

![]

Answer 1

Question 3) : NO, it is not a well-formed formula.

$f_1^2$ is a *function symbol (the first in the enumeration of bynary ones) : it take as "input" a term (variable or constant) an gives as "output" another term (i.e. a "name").

Thus, $f_1^1(x_2,x_3)$ is a term and not a formula and the syntax of the connective "$\rightarrow$" is :

$A \rightarrow B$,

where $A$ and $B$ must be formulas.

About Question 2) : it is not clear to me how to interpret the statement of the problem.

The formula :

$\lnot ((x_1 < x_2) \rightarrow (x_1⋅x_3 > x_2⋅x_3))$

is clearly satisfiable; let $x_1 := 1$, $x_2 := 2$ and $x_3 := 3$, then :

$(1 < 2) \rightarrow (1.3 > 2.3)$ i.e. $(1 < 2) \rightarrow (3 > 6)$

is false; thus its negation : $\lnot [(1 < 2) \rightarrow (3 > 6)]$ is true.

In conclusion, having found an interpretation with domain the set $\mathbb N$ of natural numbers where the formula is true, it is satisfiable.

But about tautology ? A tautology (or valid formula) is a formula which is true in all interpretations; but the formula is basically :

$\lnot (p \rightarrow q)$

and this is not a tautology (and neither a contradiction). Furthermore, a contradiction is a formula which is false for every interpretation; thus, what is the meaning of :

find an "examples of [an] interpretations [such that the formula is a] contradiction" ?

We have found and interpretation (in $\mathbb N$) of the formula which satisfy it; thus, being true in at least one interpretation, the formula obviously is not a contradiction.