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
0 answers

Contingent formula proofs

I have $A$ and $B$ that are contingent formulas. I have to prove that $A \land B $ can not be logically true and $A \lor B$ can not be logically false. How to start unfolding these questions? I know that a formula is logically false iff it is not…
0
votes
1 answer

When a set of propositions is said to be consistent?

Suppose I am given a set of propositions, and I am asked to find whether they are consistent of not? Can someone explain with an example. What does it actually mean when we say that this set of proposition is consistent?
Maninder
  • 31
  • 4
0
votes
1 answer

continuous function question

Assume that function $f$ is continuous at $x=0$. Prove that the function $f(x)=a^x$ for $a>0 $, is continuous at every real number. I know that $f$ is continuous at 0 if and only if 0 is in the domain of $f$ and $lim_(h→0)⁡〖{f(0+h)-f(0) ]=0〗$. But…
0
votes
0 answers

Dual of Propositional Formula

I have a question regarding an older question on StackExchange, because the answers are confusing me. Duality discrete math problem How do I create the dual of a term? 1) A = A and B , Ad = A or B 2) A = A and B , Ad = not A or not B
0
votes
3 answers

I want to prove $P$ is true (by contradiction). What happens if I deduce $Q$ from $\lnot P$, knowing $\lnot Q$, then replace $Q$ with $P$?

I have a quick question about reasoning by contradiction. Suppose I want to prove that a proposition $P$ is true (by contradiction). I will suppose that $\neg P$ is true and I will try to deduce that a proposition $Q$ is true, knowing that $\neg Q$…
0
votes
0 answers

completeness proof propositional logic Chiswell and Hodges´ book

I have a doubt about the completeness proof of propositional logic that appears in Chiswell and Hodges´ book. In page 93, case 2, i) I don´t understand why I can replace χ_1 by χ_1 and χ_2, because I don´t know if the rules for and introduction are…
0
votes
0 answers

Construct proofs for the following sequents, using only primitive inference rules

1.(P & R) → S, S ↔ T, ─T ├ R → ─P P v Q, P → (T → S), P → T, S ↔ Q ├ S any help will be greatly appreciated.
0
votes
2 answers

If $\Sigma=\lbrace(\neg\alpha),(\neg\beta),(\alpha\vee\beta)\rbrace$, show that $\Sigma$ is inconsistent.

If $\Sigma=\lbrace(\neg\alpha),(\neg\beta),(\alpha\vee\beta)\rbrace$, show that there is some formula $\theta$ such that $\theta$ and $(\neg\theta)$ can be deduced from $\Sigma$ (i.e., that $\Sigma$ is inconsistent) I understand I must come up…
0
votes
0 answers

Prove A → (A ∧ B) ∨ (A ∧ ¬B) using classical logic

I've tried to do this by assuming A, then using the law of excluded middle to get B ∨ ¬B. From here I plan on using or elimination to get A ∧ B then or introduction to get (A ∧ B) ∨ (A ∧ ¬B). I can get a proof of B → A ∧ B but not a proof of ¬B → A…
GXT
  • 9
0
votes
0 answers

Propositional calculus-Valuation of a group of propositions

I've encountered these two statements below, and I fail to understand why one of them is true and the other isn't. Let $X_1,X_2$ be groups of propositions,and $Z_1,Z_2$ be their satisfying groups of valuation then: $Z_1 \cap Z_2$ satisfies $X_1 \cap…
0
votes
3 answers

What is the fastest way for a person to check whether the following propositional logic formula is a logical consequence of the theory?

I have the following propositional logic theory: T = {$(A\vee B)\wedge\neg C, B\rightarrow (D\vee C), A\leftrightarrow B$} I have to answer what of the following formulas is a logical consequence of this theory: $\neg B$ $\neg C$ $C$ $A$ I know…
TKN
  • 757
0
votes
2 answers

Solving Knight and knaves using rules of inference

There are two tribes living on the island of Knights and Knaves: knights and knaves. Knights always tell truth and knaves always lie. You encounter two people A and B. What are A and B if A says, “B is a knight”, and B says, “The two of us are…
JanusP
  • 85
0
votes
1 answer

What is the minimal disjunctive normal form of this propositional logic formula?

I have the following formula: $(\neg A\land B\land C)\vee (\neg A\land B\land \neg C)\vee (\neg A\land \neg B)\vee (A\land C)\vee (A\land\neg C)$ After I did a Karnaugh Map for this formula I found out it is a tautology (in other words - all squares…
TKN
  • 757
0
votes
1 answer

Propositional Resolution Question

Given the premises $(p ⇒ q)$ and $(r ⇒ s)$, use Propositional Resolution to prove the conclusion $(p ∨ r ⇒ q ∨ s)$.
0
votes
0 answers

Propositional logic a or b or TRUE

If I have a formula $a \vee b\vee True $ What's the number of states where this is true ? Does the W even matter? Or is it for cases where a and b are 0 and the whole function is true, due to the W ?
Rapiz
  • 115