Skip to content

WA5. Logic

Task 1

Explain the concept of predicate logic. Explain the difference between propositional logic and predicate logic with simple examples. (Ensure that you do not take the same examples discussed in the reading assignments).

According to (Levin, 2021, p.199), A proposition is a statement that can be exactly true or exactly false; and propositional logic is the branch of logic that is concerned with the relationships between these propositions. The truth values of each proposition -and then the truth value of the compound proposition- is final and NOT ambiguous, as opposed to predicate logic.

Also according to (Levin, 2021, p.199), A predicate is a statement that can be true or false depending on some variables. A predicate logic is a branch of logic that is concerned with the relationships between these predicates. The truth values of each predicate -and then the truth value of the compound predicate- can change according to the values of the variables. The predicate logic extends the propositional logic and all the laws of propositional logic are valid in predicate logic.

As an example, let’s consider the following propositions:

  • \(P\): “I am a student at UoPeople”
  • \(Q\): “I am a teacher at UoPeople”

Assuming that the one can not be a student and a teacher at the same time in the same program; there are some compound statements that express this assumption:

  • \(P \land Q\) is always false.
  • \(P \land \neg Q\) is always true.

While we can demonstrate the predicate logic using similar examples; let’s consider the following predicates:

  • \(P(x)\): “x is a student at UoPeople”
  • \(Q(y)\): “y is a teacher at UoPeople”

Considering that \(x\) and \(y\) are variables indicating people, the truth values of the compound predicates can change according to the person in question; but in we are confident that the following compound predicates resolve to a value (as we know the university running, thus it must have students and teachers):

  • \(\exists x, y ∈ U\) such that \(P(x) \land Q(y)\) is true, that is, there is a student and a teacher at UoPeople; where U is the set of all people at UoPeople.

Task 2

Find the simplified proposition to the following compound proposition using basic logical laws. Show all the steps and mention all the laws associated with that step wherever applicable.

\[( P \lor \neg Q ) \rightarrow (P \land Q)\]

I will be using the following laws (Doerr & Levasseur, 2022):

The starting point is the conditional equivalence law: \(x \rightarrow y \Leftrightarrow \neg x \lor y\) considering that \(x = ( P \lor \neg Q )\) and \(y = (P \land Q)\), we can rewrite the compound proposition as:

\[ \begin{aligned} ( P \lor \neg Q ) \rightarrow (P \land Q) &\Leftrightarrow \neg ( P \lor \neg Q ) \lor (P \land Q) \text{ ........ Conditional equivalence } \\ &\Leftrightarrow (\neg P \land Q) \lor (P \land Q) \text{ ........... De Morgan's law } \\ &\Leftrightarrow (Q \land \neg P) \lor (P \land Q) \text{ ........... Commutative law } \\ &\Leftrightarrow Q \land (\neg P \lor P) \text{ ..................... Distributive law } \\ &\Leftrightarrow Q \land 1 \text{ .................................. Negation law } \\ &\Leftrightarrow Q \text{ ......................................... Identity law } \\ \end{aligned} \]

Thus the final simplified proposition is \(Q\).

References

  • Doerr, A., & Levasseur, K. (2022). Applied discrete structures (3rd ed.). licensed under CC BY-NC-SA. https://discretemath.org/ads/chapter_7.html.
  • Levin, O. (2021). Discrete mathematics: An open introduction (3rd ed.). licensed under CC 4.0.