Matrix method

The matrix method is a decision-making process for the validity of a propositional logic statement . It can be used to decide whether a statement is always true - i.e. for any variable assignment.

Further propositional decision procedures are the similarly simple truth tables , binary decision diagrams and Davis-Putnam procedures . On the theoretical side, the satisfiability problem of propositional logic , which is equivalent to the decision problem, is of great importance.

Complete matrix method

One way of checking the general validity of a statement is to evaluate the statement for all possible variable assignments and to see whether it always comes out true . In the following, a different combination of variable assignments is noted in each line. This assignment is under the variables themselves. Using the value tables for the joiners , the individual terms (here in brackets) are evaluated and the result is written under the joiners.

Example 1:

${\displaystyle (}$	${\displaystyle p}$	${\displaystyle \rightarrow }$	${\displaystyle q}$	${\displaystyle )}$	${\displaystyle \vee }$	${\displaystyle (}$	${\displaystyle q}$	${\displaystyle \rightarrow }$	${\displaystyle p}$	${\displaystyle )}$
	w	w	w		w		w	w	w
	w	f	f		w		f	w	w
	f	w	w		w		w	f	f
	f	w	f		w		f	w	f

The tested expression is valid, because in the column under the main junction there are only w's, i.e. H. the evaluation of the formula always gives true .

Example 2:

${\displaystyle (}$	${\displaystyle p}$	${\displaystyle \rightarrow }$	${\displaystyle q}$	${\displaystyle )}$	${\displaystyle \vee }$	${\displaystyle (}$	${\displaystyle q}$	${\displaystyle \land }$	${\displaystyle p}$	${\displaystyle )}$
	w	w	w		w		w	w	w
	w	f	f		f		f	f	w
	f	w	w		w		w	f	f
	f	w	f		w		f	f	f

The expression tested in example 2 is not valid, because there is an assignment for which the statement does not evaluate to be too true .

Abbreviated matrix method

A shorter method is as follows. One assumes that the statement is wrong and tries to show a (semantic) contradiction.

Note that the method is not as easy for all junctions as in the following example! For example, if you have an expression of the type , both the possibility and the fact that both cases would satisfy the assumption may have to be checked to prove the existence of a contradiction . ${\displaystyle X\wedge Y}$ ${\displaystyle X=w,\ Y=f}$ ${\displaystyle X=f,\ Y=w}$ ${\displaystyle X\wedge Y=f}$

Example 1:

${\displaystyle (}$	${\displaystyle p}$	${\displaystyle \rightarrow }$	${\displaystyle q}$	${\displaystyle )}$	${\displaystyle \vee }$	${\displaystyle (}$	${\displaystyle q}$	${\displaystyle \rightarrow }$	${\displaystyle p}$	${\displaystyle )}$
					f
		f						f
	w		f				w		f

Assuming that the expression is false, one arrives at the contradiction that (and also ) “simultaneously” must be both true and false. ${\displaystyle (p\rightarrow q)\vee (q\rightarrow p)}$ ${\displaystyle p}$ ${\displaystyle q}$

Example 2:

${\displaystyle (}$	${\displaystyle p}$	${\displaystyle \rightarrow }$	${\displaystyle q}$	${\displaystyle )}$	${\displaystyle \vee }$	${\displaystyle (}$	${\displaystyle q}$	${\displaystyle \land }$	${\displaystyle p}$	${\displaystyle )}$
					f
		f						f
	w		f
							f		w

Assuming that the expression is wrong, there is no contradiction. Any assignment that assigns the value w and the value f is a refuting assignment. ${\displaystyle (p\rightarrow q)\vee (q\land p)}$ ${\displaystyle p}$ ${\displaystyle q}$

Syntactic decision-making procedures

• Hilbert calculus
• Tableau calculus
• Natural Closing Systems (SNS)
• Sequence calculus

See also

• Calculus
• Proof theory

source

• Horst Wessel: Logic. VEB Deutscher Verlag der Wissenschaften, Berlin 1984, p. 60 ff.