Where i went wrong in this First Order Logic problem?

Question

According to me it's option A,

Steps :

To make this predicate false we should get second part to be false when first part is true.

Assuming $\exists x [\lnot p(x) \land \lnot q(x)]$

Which is making second part false at the same time $\forall x[p(x) \lor Q(x)]$ become false also, resulting overall predicate become true.

But the answer says it's B, can you explain where i went wrong in the solution.

[i didn't checked for option B, i just want to know why not A]

Update :

Now i'm having problem to invalidate the option $C$.

Answer 1

For A let P(x) mean x is even, Q(x) mean x is odd. Then the implication in A has the assumption true but conclusion false.

Edit: The universal set I was taking is the set of integers. Any subset of that having at least one even and at least one odd woud also work.

Answer 2

For $A$: Consider the set $S=\{(x,y)\in\Bbb{R}^2:x=0 \text{ or } y=0\}$ (i.e. $S$ is the union of the $x$ and $y$ axes). Then let $P(x,y)\equiv x=0$ and $Q(x,y)\equiv y=0$ be the predicates. By definition $S$ satisfies $\forall_{(x,y)} P(x,y)\vee Q(x,y)$, but neither satisfies $\forall_{(x,y)} P(x,y)$, since $(1,0)\in S$ and $\neg P(1,0)$, nor (symmetrically) does it satisfy $\forall_{(x,y)}Q(x,y)$. Hence $S$ with these predicates does not satisfy $(\forall_{(x,y)} P(x,y))\vee(\forall_{(x,y)}Q(x,y))$.

For $C$: Let $X$ be a finite set, $f:X\to X$ a function. Let $P(x)\equiv \exists_y f(y)=x$ (i.e. $P$ is true if $x$ is in the image of $f$) and let $Q(x)\equiv f(y)=f(z)=x \implies y=z$ (i.e. $Q$ means $x$ is the image of at most one element of $X$).

Then $\forall_x P(x)$ means that $f$ is surjective, and since $X$ is finite, that means $f$ is injective as ell, so we have $\forall_x Q(x)$. Thus $(\forall_x P(x))\implies (\forall_x Q(x))$, however, if we only look at a single $x$, knowing $P(x)$ does not imply $Q(x)$, since $X$ could have more than one element and $f$ could be the constant function that sends every element of $X$ to $x$, then we have $P(x)$ but not $Q(x)$, so it is not the case that $P(x)\implies Q(x)$, so it is not the case that $\forall_x (P(x)\implies Q(x))$ even though it is the case that $(\forall_x P(x))\implies (\forall_x Q(x))$. Thus C is false.

Answer 3

Let's say the universe of xs is the universe of employees of a company, and that P(x) means "x is male" and Q(x) means "x is Hungarian".

To prove that a formula is not always true, it's sufficient to imagine a situation (a "model" -- I don't know if you've covered models) in which the formula is false.

Here are the situations for the not-always-true ones:

(A): All the employees are either male or Hungarian, and there is at least one non-Hungarian male and one Hungarian female employee. Then the LHS (left-hand side) is true, but the RHS is false because it says that either all the employees are male, or all are Hungarian.

(C): The LHS is saying "If all the employees are male, then all the employees are Hungarian". This is true if NOT all the employees are male, because F=>T is T. So the invalidating situation is when not all the employees are male, but there is at least one non-Hungarian male employee. The LHS is true, but the RHS says "Every male employee is Hungarian", which is false.

(D): The LHS is saying "If all the employees are male, then all the employees are Hungarian, and vice versa". This is true if not all the employees are male AND not all the employees are Hungarian (see the answer to C). So in the invalidating situation, there is at least one female employee, at least one non-Hungarian employee, and at least one male employee who is not Hungarian. The LHS is true, but the RHS says "Every male employee is Hungarian, and every Hungarian employee is male"; we only need one of those statements to be false to make the whole statement false.

In contrast, the LHS of (B) is saying "Every male employee is Hungarian". If we assume that, and then further assume that all the employees are male, then we must conclude that all the employees are Hungarian.

Answer 4

Invalidating c) is the most tricky one, since you'll have to rely on the fact that any consitional is true as soon as its antecedent is false.

So, if you take $P(x):$ '$ x$ is a dime' and $Q(x):$ '$x$ is a nickel' (in the domain of all coins), then:

$\forall x P(x) \rightarrow \forall x Q(x)$ is true, since $\forall x P(x)$ is false

but

$\forall x (P(x) \rightarrow Q(x))$ is false