Question

Simplify the following propositions (i.e. find a simpler equivalent proposition). (a) \((\varphi \rightarrow \psi) \wedge \varphi\), (b) \((\varphi \rightarrow \psi) \vee \neg \varphi\), (c) \((\varphi \rightarrow \psi) \rightarrow \psi\), (d) \(\varphi \rightarrow(\varphi \wedge \psi)\), (e) \((\varphi \wedge \psi) \vee \varphi\), \((\mathrm{f})(\varphi \rightarrow \psi) \rightarrow \varphi\)

Short answer

(a) \(\psi \wedge \varphi\), (b) \(\neg \varphi \vee \psi\), (c) \(\psi\), (d) \(\varphi \rightarrow \psi\), (e) \(\varphi\), (f) \(\neg \psi \rightarrow \varphi\)

Step-by-step solution

Analyze Proposition A

Given: \((\varphi \rightarrow \psi) \wedge \varphi\).A logical implication \(\varphi \rightarrow \psi\) can be rewritten as \(eg \varphi \vee \psi\).So, the proposition becomes \((eg \varphi \vee \psi) \wedge \varphi\).Using the distributive law, we get \((eg \varphi \wedge \varphi) \vee (\psi \wedge \varphi)\).Any proposition \(eg \varphi \wedge \varphi\) is a contradiction (False), leaving us with \(\psi \wedge \varphi\) as the simplified version.

Analyze Proposition B

Given: \((\varphi \rightarrow \psi) \vee eg \varphi\).Rewrite \((\varphi \rightarrow \psi)\) as \((eg \varphi \vee \psi)\).The proposition becomes \((eg \varphi \vee \psi) \vee eg \varphi\).By the idempotent law, \((eg \varphi \vee eg \varphi) = eg \varphi\), so we have \(eg \varphi \vee \psi\) as the simplified version.

Analyze Proposition C

Given: \((\varphi \rightarrow \psi) \rightarrow \psi\).Using the implication equivalence, \((\varphi \rightarrow \psi)\) can be seen as \((eg \varphi \vee \psi)\).Now consider that \((eg \varphi \vee \psi) \rightarrow \psi\) is true by tautology when \(\psi\) is true, and if \(eg \varphi\) is true, \(\varphi\) is false, making the implication true regardless.Thus, the simplified form is just \(\psi\).

Analyze Proposition D

Given: \(\varphi \rightarrow (\varphi \wedge \psi)\).This states that if \(\varphi\) is true, then both \(\varphi\) and \(\psi\) are true, which simplifies to checking if \(\varphi\) is always sufficient for itself.Since \(\varphi\) itself implies \(\varphi \wedge \psi\) can only be valid if \(\varphi\) is false, it essentially means \((eg \varphi) \vee (\varphi \wedge \psi)\).This simplifies logically to \(eg \varphi \vee \psi\), which is \(\varphi \rightarrow \psi\).

Analyze Proposition E

Given: \((\varphi \wedge \psi) \vee \varphi\).Utilize the distributive law: \((\varphi \wedge \psi) \vee \varphi\) can be rearranged as \(\varphi \vee (\psi \wedge \varphi)\).Using absorption law, \(\varphi \vee (\varphi \wedge \psi) = \varphi\).Thus, the proposition simplifies to \(\varphi\).

Analyze Proposition F

Given: \((\varphi \rightarrow \psi) \rightarrow \varphi\).Rewriting the propositions: \(\varphi \rightarrow \psi\) is \(eg \varphi \vee \psi\).Now, \((eg \varphi \vee \psi) \rightarrow \varphi\) simplifies using material implication and distribution, giving us \(eg \varphi \rightarrow \varphi\) if \(eg \psi\) holds.Thus, it simplifies to checking for a contradiction in \(\varphi \wedge eg \varphi\), so the simplified form is \(eg \psi \rightarrow \varphi\), if using pure logic translation it isn't vacuously true.

Key concepts

Logical Equivalence

In propositional logic, logical equivalence occurs when two statements have the same truth value in all possible scenarios. For instance, when we transform a compound statement into another form without changing its meaning or truth value, we maintain logical equivalence.

Logical equivalences are verified using truth tables where two statements result in the same outputs or by using transformation laws such as De Morgan's.

For example, using logical equivalence,

• "P implies Q" ( \(P \rightarrow Q\))
can be rewritten as
• "not P or Q" (\(eg P \vee Q\)).

This alternative representation helps in simplifying complex logical propositions, making them easier to work with, especially in computer science and mathematics.

Tautology

A tautology is a proposition that is always true, regardless of the truth values of its components. In logical expressions, tautologies are crucial as they help in proving the logical validity of arguments.

Tautologies have truth tables where all combinations of truth values for variables result in the overall expression being true.

A common example is:

• "P or not P" ( \(P \vee eg P\))

This is a classic tautology because it covers all possibilities for P: it's either true or false, thus ensuring the statement is always true. Understanding tautologies aids in creating logical constructs where unnecessary conditions are removed yet the validity is preserved.

Implication Equivalence

Implication equivalence is about understanding how implications can be interchanged or expressed differently without altering their inherent meaning.

An implication \(P \rightarrow Q\) suggests that if P is true, Q must also be true. But this can also be expressed as \(eg P \vee Q\), using logical equivalence.

• For example, rewriting \((\varphi \rightarrow \psi)\) as \((eg\varphi \vee \psi)\)

shows flexibility in logical representation. This aids in simplifying logic statements, especially in proofs or algorithm design.

Understanding these equivalences is central to dissecting the logical structure of arguments, particularly when linking multiple statements using logical connectives.

Distributive Law

In logical expressions, the distributive law allows us to transform expressions for simplification, much like in arithmetic. This principle makes it easier to rearrange and simplify logical propositions.

Generally, the distributive law in logic involves how conjunction (\(\land\)) and disjunction (\(\lor\)) interact. For instance, you can move a conjunction across a disjunction as follows:

• (P and (Q or R))
  is equivalent to
  ((P and Q) or (P and R)).

Similarly, a disjunction can distribute over a conjunction.

Understanding the distributive law is especially helpful in breaking down complex propositions into simpler, more manageable components, aligning with logical equivalence and aiding in the creation of easier proofs and logical arguments.