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

Mathematical Logic : Implication

consider the statement, if today is Monday then tomorrow is Tuesday how is the third condition true in this case?
user91187
0
votes
1 answer

In propositional logic, is F ⊨ ¬G the same as F ⊭ G?

I'm trying to understand this proof in Shawn Hedman's book, "A First Course in Logic": Proposition 1.19: For any formulas F and G, G is a consequence of F if and only if F → G is a tautology. Proof: We show that $F → G is not a tautology if and…
toraritte
  • 163
0
votes
0 answers

Propositional logic in other domains

The transfer of propositional logic to other domains has been investigated (as mentioned here for example). By domain here I mean an area that has some regularities and is reflected, for example, in the theory of multiple intelligences. I see that…
Juandev
  • 101
0
votes
1 answer

Is the choice between conjunction and implication valid according to natural language?

Consider the following two statements - "All apples are delicious" "Some apples are delicious" and, consider the following four domain sets - {delicious apple 1, delicious apple 2, delicious orange, unpleasant mango} {delicious apple, unpleasant…
0
votes
0 answers

Can be use substitution for existential elimination in Horn clause?

I have a question that when prove and use forward and backward reasoning or resolution ,that in the clause have exitential quantifier, so can I not to use skolemization for substiution then just put it its to rule base and prove its like any horn…
chews
  • 23
0
votes
2 answers

Can $\neg$ be defined only using $\{ \wedge , \vee\}$?

In propositional logic, can '$\neg$' symbol be defined only using $\{ \wedge , \vee\}$ ? I don't think that $\neg$ (negation) can defined using the conjunction and disjunction operators, since its independently mentioned in the five common logic…
V.G
  • 4,196
0
votes
6 answers

Why isn't the negation of "p implies q" "p implies not q"?

My line of reasoning is that if it is not possible for both statements to be true at the same time and both statements to be false at the same time, then the two statements are negations of each other. Clearly, it is not possible for "p implies q"…
0
votes
1 answer

Logical equivalence of propositions

Lets suppose we have two propositions p and q: p = a ^ b q = c ^ d Are these propositions logically equivalent? Both propositions define the same boolean function F = {((0, 0), 0), ((0, 1), 0), ((1, 0), 0), ((1, 1), 1)}, so they seem to be…
user341
  • 93
0
votes
1 answer

A binary formula to check if two binary variables are equal

Suppose I have $X,Y$ that are equal to one or zero. Is it possible to formulate a binary variable that is equal to $1$ if both $X,Y$ have the same value (i.e. $X=0$, $Y=0$ or $X=1$, $Y=1$) or equal to $0$ if they are different (i.e. $X=1$, $Y=0$ or…
0
votes
0 answers

Law of contrapositive - what's wrong with my proof?

Can I prove that $A \implies B$ implies $\neg B \implies \neg A$ in this particular way? I assume $A \implies B$ and $ \neg (\neg B \implies \neg A)$ and derive a contradiction. Is this ok?
Adam
  • 3,422
  • 1
  • 33
  • 50
0
votes
1 answer

Do There Exist Normal Multi-Valued Interpretations for the Equivlaential Calculus?

Suppose we define a propositional calculus, just by its (object language) theorem set and its rules of inference. For example, suppose we define the C-N propositional calculus by the set of theorems deducible from CCpCqrCCpqCpr…
0
votes
1 answer

Is $(A \land B)$ a form of $(p \land p)$?

This question is related to my previous question on forms of statements, here: Rigorous definition of the set of forms of a propositional formula. Consider the propositional formula $(p \land p)$, where $p$ is a propositional atom. It is of the form…
user107952
  • 20,508
0
votes
1 answer

Three people logic puzzle

There are three doctors. I ask them who can help me? Each doctor says “I am the only one who can help you, because I am the only one who will tell you the truth; the other two doctors are liars!” I need to create a truth table to see which doctors…
0
votes
1 answer

What is the formal, mathematical definition of truth tables?

Suppose $A$ is a propositional formula where precisely $n$ propositional atoms appear. For example, letting $n$ be $3$, $((p \land q) \rightarrow r)$ is an example of such a formula. My question is, what is the formal definition of a truth table for…
user107952
  • 20,508
0
votes
0 answers

In a truth table, do you have to duplicate columns for duplicate occurrences of formulas?

Consider the propositional formula $((P \land Q) \vee (P \land Q))$. Suppose I were to make a truth table for that formula. I would first make two columns of four rows, representing the possible assignments of $P$ and $Q$ to true and false. Then, I…
user107952
  • 20,508