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
0
votes
1 answer

Signatures in Propostional logic (Hodges and Chiswell Exercise 3.4.4)

The exercise 3.4.4 of Mathematical Logic by Hodges and Chiswell is like that: "Let $\rho$ and $\sigma$ be signatures with $\rho \subseteq \sigma$ (a) Suppose $D$ is a $\sigma$-derivation, and $D'$ is got from $D$ by writing $\perp$ em place of…
0
votes
1 answer

How to "flatten" arbitrarily nested propositional logic formula, given conjunction/disjunction only have a left and a right?

Since it appears you can have arbitrarily deeply nested conjunctions and disjunctions (see this question), such as: $$(((A ∧ B) ∨ (C ∧ (D ∨ E)) ∧ (F ∧ (G ∨ H)))$$ How do you "flatten" it, if you have the constraint that both conjunction and…
Lance
  • 3,698
0
votes
1 answer

Can you have nested conjunctions and disjunctions in propositional logic?

For example, can you do something like this in propositional logic? AND(OR(AND(A, B), AND(C, OR(D, E))), AND(F, OR(G, H))) Or put more visibly as a tree: AND OR AND(A, B) AND(C, OR(D, E))) AND(F, OR(G, H))) As propositional logic, it…
Lance
  • 3,698
0
votes
1 answer

Prove that the proposition $p\to(q\to(p\wedge q))$ is a tautology by using identities.

This is a homework question that I am struggling with. I can use properties to expand out or simplify this proposition, but how does one prove that it is a tautology without using a truth table or some other form of concrete values? I have proven…
0
votes
1 answer

Definition of logical equivalence

I'm following a book on Discrete Mathematics, and am having trouble understanding a nuance. Two statement forms are called logically equivalent if, and only if, they have identical truth values for each possible substitution of statements for…
ankush981
  • 2,033
0
votes
0 answers

Construction Dilemma Holds Both Ways?!!

In page 37 of A Transition to Advanced Mathematics, the authors intend to prove a statement of general logical form $P\vee Q\Rightarrow R_{1}\vee R_{2}$ where $P,Q,R_{1},R_{2}$ are predicates, "...The proof method we choose is to show that…
mali1234
  • 344
0
votes
2 answers

Boolean Algebra Maxterms and Minterms

while I was doing my homework I got confused since I used two ways to do an equation and gives me different minterm sets. The following are my work, please tell me where I made a mistake. The original question is…
0
votes
0 answers

What's the relationship between an answer set and a model?

I'm very new to mathematical logic and recently I've encountered with the notion of ASP (answer set programming) when I'm learning classical logic. My question is that I don't quite get the point why there comes up the notion of ASP and I don't…
0
votes
1 answer

Deriving intersection of two truth sets

$ \newcommand{\Set}[2]{% \{\, #1 \mid #2 \, \}% }$ Let $A = \Set{x}{P(x)}$, $B = \Set{x}{Q(x)}$. We know by definition that $$ A \setminus B = \Set{x}{P(x) \land \lnot Q(x)}.$$ Since $X \cap Y = X \setminus (X \setminus Y)$ for two sets $X$ and…
0
votes
1 answer

How do I Finish Simplifying this Laws of Propositional Logic Problem?

In my Discrete Mathematics class I have just started learning about the laws of propositional logic. I've got about halfway through a problem but am now stuck for a while now and I don't understand where to go/what law to use. Any guidance would be…
0
votes
1 answer

To prove $p⊕q$, does it suffice to prove $p\implies \sim q$ and $\sim p\implies q$?

By p⊕q, also written p xor q, I mean either $p$ or $q$ but not both; and I use the symbol $\sim $ to negate propositions.
user923938
0
votes
1 answer

Is the conclusion of this proposition correct?

$¬Q \lor (R \land S) $ $P \lor Q $ $P \land R \land S$ clause 1 and clause 2 can create clause 3?
Dan Leo
  • 23
0
votes
2 answers

How to prove this logical consequence vs. equivalence

I need to prove that the formula $P \leftrightarrow Q$ is a logical consequence of, but not logically equivalent, to the conjunction of the following: $Q \rightarrow R$ $R \rightarrow (P \land Q)$ $P \rightarrow (Q \lor R)$ I've been able to…
0
votes
1 answer

Craig's interpolation theorem counterexample?

I'm considering the following problem from Elliott Mendelson's book "Introduction to Mathematical Logic". The proof of (b) he gives is as follows: A conjunction $\mathscr{E}$ of the form $B_1^{*}\wedge B_2^{*}\dots\wedge B_n^{*},$ where each…
Zerkoff
  • 489
0
votes
1 answer

Propositional Logics

Any one that can work out the details that are missing from this: (¬B1 ∧¬¬B2 ∧¬B2)∨(¬¬B1 ∧¬B2 ∧¬B2)∨(¬¬B1 ∧¬¬B2 ∧B2) to this: (B1 ∧ ¬B2) ∨ (B1 ∧ B2) I know that they are of course using Double Negation law - but i don't get it afterwards. Is it the…
GAUSS
  • 25