1
$\begingroup$

Let F be a unary propositional connective, such that F(p) is always false, regardless of the value assigned to p.

i. Give the truth table for F. (Hint: how many lines does it have?)

I have:

p | F(p)

T | F

F | F

Is this right?

ii. Write out a formal inductive definition for the set of well-formed propositional formulas thet use only the connectives F and →.

Can someone help me with this one? I have no idea what i have to do for this one.

iii. Show that {F, →} is an adequate set of connectives.

I try to show all formulas can be made from F and -> but I can not find the equivalent of A and B. (I have not A = A -> F(A))

$\endgroup$
1
$\begingroup$

i. Yes, that is correct.

ii. You have to make a description of how to write well-formed formulas. For example, in the given language (with propositional variables, F and $\rightarrow$), $p \rightarrow F(q)$ and $F(r)$ are examples of well formed formulas, while $p \wedge q$ and $p \rightarrow Fq$ are non-examples.

The exact style of definition depends on your teacher's requirements. This is one way to go:

X is well formed if:

  • X is a propositional variable ($p, q, r, ...$)
  • X is of form ($G \rightarrow H$), where $G$ and $H$ are well formed formulas
  • X is of form $F(G)$, where $G$ is a well formed formula

(you can also add a note that outermost brackets can be omitted, then $G \rightarrow H$ will be a wff, but this must be separated from definition to avoid ambiguous expressions like $A \rightarrow B \rightarrow C$)

iii. $G \vee H \equiv \neg G \rightarrow H \equiv (G \rightarrow F(G)) \rightarrow H$

One simple way to get conjunction is via De Morgan, and to get $\leftrightarrow$ use previously defined $\wedge$ and $\rightarrow$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy