3
$\begingroup$

Which of the following propositional logic statements are true and why?

  1. $(∀x(P(x)⟹Q(x)))⟹((∀xP(x))⟹(∀xQ(x)))$
  2. $(∀x(P(x))⟹∀x(Q(x)))⟹(∀x(P(x)⟹Q(x)))$
  3. $(∀x(P(x))⇔(∀x(Q(x))))⟹(∀x(P(x)⇔Q(x)))$
  4. $(∀x(P(x)⇔Q(x)))⟹(∀x(P(x))⇔(∀x(Q(x))))$

  5. Are their any standard laws/rules of distribution of universal quantifier over conditional and binconditional that can help me solve this?

  6. Also rules for distribution of existential quantifier over conditional and binconditional?

Recently I came across distribution of quantifiers over $\vee$ and $\wedge$, which gave set theoretic interpretation of them as follows:

  • $((∀x)G(x)∨ (∀x)H(x))→ (∀x)(F(x)∨ G(x))$

    In set theoretic terms, if we have that $(f(G) = D ∨ f(H) = D)$, then we have $(f(G) ∪ f(H)) = D$

  • $(∃x)(G(x)∧ H(x))→((∃x)G(x)∧ (∃x)H(x))$

    In set theoretic terms, if we have that $(f(G) ∩ f(H)) ≥ 1$, then we have $(f(G) ≥ 1 ∧ f(H) ≥ 1)$

Can we say similar for distribution of quantifiers over conditional and biconditional (just to bring in more clarity)?

$\endgroup$
5
  • $\begingroup$ The above formulas are not propositional, since they use quantifiers. They are just formulas of first-order logic. $\endgroup$ Commented Jan 1, 2016 at 21:23
  • $\begingroup$ Do you want me to change the title to something else? $\endgroup$
    – Mahesha999
    Commented Jan 1, 2016 at 21:25
  • $\begingroup$ Yes, the title is misleading, as well as the tag "propositional calculus". $\endgroup$ Commented Jan 1, 2016 at 21:27
  • 1
    $\begingroup$ Does the new one makes sense "Rules of distribution of quantifiers over conditional and biconditional makes sense?" $\endgroup$
    – Mahesha999
    Commented Jan 1, 2016 at 21:31
  • $\begingroup$ Now the title is ok for me. $\endgroup$ Commented Jan 1, 2016 at 21:33

1 Answer 1

1
$\begingroup$

Formulas (1) and (4) are valid, i.e. they are true in every first-order $\mathcal{L}$-structure.

Formulas (2) and (3) are not valid, i.e. there exists a $\mathcal{L}$-structure in which they are not true. For instance, take the $\mathcal{L}$-structure $\mathcal{N}$ whose domain is $\mathbb{N}$ and whose interpretation of $P$ is $2\mathbb{N}$ (the set of even natural numbers), and whose interpretation of $Q$ is $\mathbb{N} \smallsetminus 2\mathbb{N}$ (the set of odd natural numbers). You have that the formula $\forall xP(x) \Rightarrow \forall x Q(x)$ is vacuously true in $\mathcal{N}$ (it claims that "if every natural number is even then every natural number is odd"), but the formula $\forall x(P(x) \Rightarrow Q(x))$ is false in $\mathcal{N}$ (it claims that "for every natural number, if it is even then it is odd"), therefore your formula (2) is false in $\mathcal{N}$. Similarly for the formula (3), since $A \Leftrightarrow B$ is equivalent to $(A \Rightarrow B) \land (B \Rightarrow A)$.

In general, when one talks about distributivity of something over something else (for instance, distributivity of $\land$ over $\lor$), one means that two formulas are logically equivalent. With this meaning, the answer to your question "Does the universal quantifier distribute over conditional or biconditional?" is negative since the formula $\forall xP(x) \Rightarrow \forall x Q(x)$ is not logically equivalent to the formula $\forall x(P(x) \Rightarrow Q(x))$ (your formula (1) is valid, but your formula (2) is not valid), and similarly the formula $\forall xP(x) \Leftrightarrow \forall x Q(x)$ is not logically equivalent to formula $\forall x(P(x) \Leftrightarrow Q(x))$ (your formula (4) is valid, but your formula (3) is not valid).

$\endgroup$
8
  • $\begingroup$ Well I have not taken a dedicated course on mathematical strucutres or read any books specifically on mathematical structures. So I am finding it difficult to deal with $L$-structure thingy... $\endgroup$
    – Mahesha999
    Commented Jan 2, 2016 at 9:10
  • $\begingroup$ ...However,if interprete $P(x)$ as "x is a boy" & "$Q(x)$ is clever". Then, $(∀x(P(x)⇔Q(x)))$ means "If any $x$ is a boy then he is clever & vice versa". This definitely implies $(∀x(P(x))⇔(∀x(Q(x))))$, "If all $x$ are boys then all are clever & vice versa". But converse does not seem valid as $(∀x(P(x))⇔(∀x(Q(x))))$ puts restriction: "if all $x$ are boys". $(∀x(P(x)⇔Q(x)))$ requires that "for any $x$, if $x$ is a boy", but does not require that "all $x$ are boys", so there may be a person who is not boy, but still $(∀x(P(x)⇔Q(x)))$ will be valid but $(∀x(P(x))⇔(∀x(Q(x))))$ will not be... $\endgroup$
    – Mahesha999
    Commented Jan 2, 2016 at 9:11
  • $\begingroup$ ...So 3 seems invalid to me, while 4 seems valid. Also what about distributing existential quantifier? $\endgroup$
    – Mahesha999
    Commented Jan 2, 2016 at 9:11
  • $\begingroup$ @PardonMeForMySuperPoorMaths: Sorry, there was a typo in my answer, now I fixed it. Your formula (4) is the "biconditional version" of your formula (1), and your formula (3) is the "biconditional version" of your formula (2). $\endgroup$ Commented Jan 2, 2016 at 10:14
  • $\begingroup$ any comment about the same but involving existential quantifier? $\endgroup$
    – Mahesha999
    Commented Jan 2, 2016 at 12:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .