1

Can you have p = not q?

Is there a rule somewhere that says you can't have this?

I'm asking this because there's a question that asks me to prove that all positive formulae are satisfiable. A positive formula is a propositional formula that doesn't have a negation anywhere in it.

But if you can define p = not q then a positive formula p & q would be unsatisfiable.

user2108462
  • 387
  • I think all the variables have to be independent? – Nishant May 22 '14 at 15:44
  • Can you cite a source please – user2108462 May 22 '14 at 15:44
  • If a formula $A := f(p_1, ... p_n)$ where $f$ is a truth-function whatever, is positive, it cannot contains $p_i$ and $\lnot p_i$. Thus (by induction ?) you can show that is always possible to define a truth-assignement $v : { p_1, ... p_n } \rightarrow { T, F }$ such that $v(A) = T$. – Mauro ALLEGRANZA May 22 '14 at 16:00

3 Answers3

4

Take any "standard" mathematical logic textbook, e.g. :

Dirk van Dalen, Logic and Structure (5th ed - 2013), page 7 :

Definition 2.1.1 The language of propositional logic has an alphabet consisting of :

(i) proposition symbols: $p_0, p_1, p_2,$ . . .,

(ii) connectives: ∧,∨,→,¬,↔,⊥,

(iii) auxiliary symbols: ( , ).

[...] The proposition symbols and $\bot$ stand for the indecomposable propositions, which we call atoms, or atomic propositions.

Definition 2.1.2 The set $PROP$ of propositions is the smallest set $X$ with the properties :

(i) $p_i \in X (i \in \mathbb N), \bot \in X$,

(ii) if $ϕ,ψ \in X$, then $(ϕ ∧ ψ), (ϕ ∨ ψ), (ϕ→ψ), (ϕ↔ψ) \in X$,

(iii) if $ϕ \in X$, then $(¬ϕ) \in X$.

With this definition, we have that a single proposition symbol $p_i$ can be a proposition but, translating into your terminology, a "complex" expression, like $(p_i \land p_j)$ or $(\lnot p_i)$ is not a propositional letter (i.e.a propositional symbol) but a formula (i.e.a proposition).

Note. In order to give a positive answer to your problem, we have to modify the above definition excluding $\bot$.

Mauro ALLEGRANZA
  • 94,169
  • So proposition symbols can only stand for atomic propositions? What's the shorthand for representing formulae then? – user2108462 May 22 '14 at 16:04
  • 1
    @user2108462 - what are you meaning with "shorthand for representing formulae" ? Usually, we use meta-variable standing for formulae. In van Dalen's textbook, greek letters like $\varphi$ and $\psi$ stand for "complex" formulae (members of the set $PROP$) built up from propositional letters with the "glue" of (one or more occurrence of) connectives. – Mauro ALLEGRANZA May 22 '14 at 16:09
  • Okay what if I set p = q? Would p not be an atomic formula then? – user2108462 May 22 '14 at 16:18
  • 1
    In the above language we do not have "="; we may have $(p_i \leftrightarrow p_j)$ which, of course, is not atomic because it is a "complex" formula. – Mauro ALLEGRANZA May 22 '14 at 16:20
1

No. A propositional variable stands for a proposition that cannot be broken down into smaller pieces. You could view "$p = \neg q$" as a definition of a compound proposition $p$, or as an assertion relating two propositional variables $p$ and $q$, but not as a definition of a propositional variable $p$.

To determine whether a compound proposition is positive, you need to break it down all the way into propositional variables. So if $p$ and $q$ are propositional variables, then $p \wedge q$ is positive, but if $p$ is a compound proposition $\neg q$, then $p \wedge q$ is equal to $\neg q \wedge q$, so it is not positive.

It would be less confusing to use different letters (e.g. $p$, $q$, etc. for propositional variables and $\varphi$, $\psi$, etc. for compound propositions,) but I don't think there is a universal standard for this.

Trevor Wilson
  • 16,989
  • So letters can both represent atomic and compound propositions or they can only represent atomic propositions? – user2108462 May 22 '14 at 16:08
  • @user2108462 It's a matter of convention. Writers should always say what they mean by a symbol and not assume that the reader knows that a particular symbol is meant to represent a particular kind of object. – Trevor Wilson May 22 '14 at 16:09
0

p&q is logically equivalent to (not q)&q which is not a positive formula. p&q without the condition of q= not p is a positive formula, with that condition it is not a positive formula and thus is not necessarily satisfiable.

user47475
  • 97
  • 1
    Where is it stated that if a positive formula is logically equivalent to a non-positive formula, then it's a non-positive formula? – user2108462 May 22 '14 at 15:50
  • A positive formula (e.g. $p$ itself) can be logically equivalent to a non-positive formula (e.g. $\neg\neg p$.) I think it's ambiguous to speak of the "condition" $q = \neg p$. If this condition is taken to be a definition of a formula $q$, then $p \wedge q$ is not a positive formula because it is equal to $p \wedge \neg p$ (not merely logically equivalent.) A different, but related, observation is that the set of formulas ${q \leftrightarrow \neg p, p \wedge q}$ is not satisfiable. – Trevor Wilson May 22 '14 at 16:17