Questions tagged [propositional-calculus]

Appropriate for questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions. Also for general questions about the propositional calculus itself, including its semantics and proof theory. Questions about other kinds of logic should use a different tag, such as (logic), (predicate-logic), or (first-order-logic).

Propositional logic is a branch of logic dealing with logical connectives and statements involving them. A logical connective connects finitely many sentences and forms a compound sentence, in a way that the truth value of the compound sentence depends only on the truth value of its constituents. The most common connectives are the binary connectives conjunction ($\land$), disjunction ($\lor$) and implication ($\rightarrow$), the unary connective negation ($\neg$), and the nullary connectives true ($\top$) and false ($\bot$).

Any proposition is considered to be either atomic (in which case it has no constituents) or compound (in which case it's formed by mean a connective using simpler propositions). A propositional model is a function assigning to each atomic proposition a truth value $0$ or $1$. The truth values of compound propositions are then determined by the truth values of their constituents. For example, if $I$ is a function assigning truth values to propositions, one would have $I(\top)=1$, $I(\bot)=0$, $I(\neg A)=1-I(A)$, $I(A\land B)=\min\big(I(A),I(B)\big)$, $I(A\lor B)=\max\big(I(A),I(B)\big)$ and $I(A\rightarrow B)=\max\big(1-I(A),I(B)\big)$. The propositions having the value $1$ for every model, are called tautologies, and those having the value $0$ for every model, are called absurdities. A central task of propositional logic is characterizing tautologies and absurdities.

5541 questions
4
votes
1 answer

How do I prove $\neg(P\land Q)\to(\neg P\lor(\neg P\lor Q))\iff(\neg P\lor Q)$ without using a truth table?

Without using truth tables prove that $$\neg(P\land Q)\to(\neg P\lor(\neg P\lor Q))\iff(\neg P\lor Q)$$ This is a question I've encountered during my examination. So basically what I did was, I took the RHS of the equation which is $\neg(P\land…
Nimrod
  • 155
4
votes
0 answers

Is the consequence relation of a finite set of boolean connectives finitely generated?

Let $S$ be the set of all n-ary functions on $\{0,1\}$ for all n, including the 0-ary functions. Let $F$ be a finite subset of $S$. Consider a countably infinite set of propositional constants $PROP$. Now, we define recursively a language on $PROP…
user107952
  • 20,508
4
votes
1 answer

Find two nonequivalent propositions which depend only on q

The question I'm stuck on is: Let $p$ and $q$ be propositions. A compound proposition $f(p,q)$ is given by $(p\vee \neg q) \Rightarrow (p \Leftrightarrow q)$. Find two non-equivalent propositions $h_1(q)$ and $h_2(q)$ which depend only on $q$, such…
Z Oj
  • 111
4
votes
4 answers

Prove that $\neg (\neg P \lor (P \land \neg Q)) \equiv P \land Q$ without using truth tables

Prove that $$\neg (\neg P \lor (P \land \neg Q)) \equiv P \land Q$$ without using truth tables. Instead, use various logic properties like De Morgan's, etc.
LizW
  • 216
4
votes
1 answer

How many equivalence classes are there under the relation of logical equivalence?

I was wondering how might one go about solving the question: How many different last columns occur among all the truth tables with propositional variables p, q, r, s? (In other words, how many equivalence classes are there under the relation of…
4
votes
1 answer

If $\models \phi \supset \psi$, then there is a propositional variable variable $p$ that occurs in both $\phi$ and $\psi$.

Full question: Suppose that $\models \phi \supset \psi$, and that $\phi$ is not a contradiction nor $\psi$ a tautology. Show that there is a propositional variable variable $p$ that occurs in both $\phi$ and $\psi$. My initial thought was just to…
user225477
3
votes
2 answers

Algebraic Solution to Prove Tautology

I need an algebraic solution to show this is a tautology: $\displaystyle [(p\lor q) \land (p \rightarrow r) \land (q \rightarrow r)] \rightarrow r$. Thanks
John
  • 39
3
votes
1 answer

Proving formula's tautology

Prove that a formula that consists only of logical equality, logical negation and has even number of propositional variables and logical negations must be tautological. I tried it out with couple of examples and it seems pretty obvious, but how…
3
votes
2 answers

Test the validity of the arguments

1) "If interest rates are low, then housing starts are up. If housing starts are up, then marriage rates are high. If interest rates are low, then the economy is good. The economy is not good. Therefore marriage rates are not high." 2) "If Sajee is…
3
votes
2 answers

valid/invalid propositional logic

I was looking into the below problem found at this site and that question is whether the given propositional logic is valid or not. I got few doubts why the You don't write a paper,however you get an extra credit. sentence has been split into two…
user91187
3
votes
0 answers

Application of the compactness theorem

In my logic book they ask me to prove the following as a consequence of the compactness theorem for propositional logic. Let $S \subseteq N$ be an infinite set. I have to show that there exists an infinite sequence of unequal binary numbers:…
user93828
  • 43
  • 2
3
votes
1 answer

Definability of Sets of Truth Assignments

I have some questions about under what conditions a set of truth assignments is the model of some set of sentences. To be more precise, suppose I'm dealing with only propositional logic. Let $K$ be a set of truth assignments, i.e. those maps…
Pachara
  • 63
3
votes
1 answer

What's the difference between Principle of bivalence and law of excluded middle?

My understanding is excluded middle stay in the syntactic level $P\,\vee \,\neg P$ while Principle of bivalence interpret $P$ and $\neg P$ to some certain meaning. But I'm not sure about it.
Yu Zeng
  • 33
3
votes
2 answers

Can I infer $P$ given only $P\to (Q\wedge R)$ and $R=true$

In an introductory class, the professor showed us the following example: Anyone who loves nature($P$) certainly also loves animals($Q$) and plants($R$). Which was translated to the expression $P\to (Q\wedge R)$, which, also sounds strange, but I'll…
Asakeron
  • 133
  • 3
3
votes
2 answers

The formula is proved tautology using Truth Table but gives another answer if solved with formula

I am trying to prove by formula that the following formula is a tautology but I am not able to do so, although I have proved it as a tautology with truth table (A∨B) ∧ (¬B∨C) → A∨C ¬((A∨B) ∧ (¬B∨C)) ∨ A∨C (¬A∧¬B) ∨ (B∧¬C) ∨ A∨C ¬A∨(B∧¬C) ∧…
Far
  • 143
1
2
3
30 31