# 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).

559 questions
191 views

### What is this property exhibited by some logical systems?

The following property exhibited by some logical systems has captured my attention: $$\forall X\; ( {\vdash x_1[X]} \implies {\vdash x_2[X]} ) \implies \forall X\; {\vdash (x_1[X]\to x_2[X])},$$ ...
95 views

### How do I translate $[(P \Rightarrow Q) \land (Q \Rightarrow T)] \Rightarrow T$ into English?

In his book, Axioms & Set Theory, Robert Andre introduces logic with this statement: If $Q$ is true whenever $P$ is true, and $T$ is true whenever $Q$ is true, then $T$ is true whenever $P$ is ...
66 views

### 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$. ...
427 views

219 views

### Does every CNF formula have an equivalent 2-CNF formula?

From Wolfram MathWorld: A statement is in conjunctive normal form if it is a conjunction (sequence of ANDs) consisting of one or more conjuncts, each of which is a disjunction (OR) of one or more ...
549 views

### How many ternary functionally complete connectives are there?

Today I was reading up once more on some of the nice results regarding functional completeness, notably Post's celebrated classification theorem with the 5 classes that need to be avoided. (See this ...
115 views

### Trouble at translating natural language to propositional logic and proving conclusion from it.

Given this set of premises: Something in the forest I hadn't observed was not the dark ruler Something which had been noted means worth to be remembered Something I had seen in the forest not ...
91 views

### Is the following derivation of Gödel's Paradox generalizable to an intuitionistic one using provability?

I will follow Goedel's original proof of Goedel's paradox located on pg. 264 of Hao Wang's A Logical Journey: From Gödel to Philosophy. With this in sight, and to also avoid confusion, I will also ...
143 views

### 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 ...
613 views

44 views

### Arguments by case

I am taking real analysis, but that is really not important.....the important part is that my professor says that one of my methods of proof is invalid. Essentially he is asking me to prove something ...
98 views

45 views

### Logical expressivity and model classes

Consider two logical languages $\mathcal L_1\subseteq\mathcal L_2$. Let the corresponding logics be semantically defined. Suppose that the correspond models depend on the language itself, but there is ...
45 views

101 views

### Sentential Logic. Reasoning.

can anybody critique, and if necessary, correct, my reasoning in the following translation? c. Either Alice has a dog and Carol has a cat, or Bob has a dog and Carol does not have a cat. This is ...
4k views

### Converting DNF to CNF and vice versa

I am fairly confident of the definition of CNF and DNF (e.g. why $(P \land Q)$ in both CNF and DNF. However, I'm a little shaky when it comes to converting between the two normal forms. Is it ...
144 views

### Different ways to define Kripke structure

The Wikipedia page https://en.wikipedia.org/wiki/Kripke_structure_(model_checking)#Example has an example of a Kripke structure $M = (S,R,L)$; however, others define Kripke structures as $M = (S,R,V)$ ...
138 views

### Are these two logical statements equal?

I found this question from a website: "Neither the fox nor the lynx can catch the hare if the hare is alert and quick." Let: P: The fox can catch the hare Q: The lynx can catch the ...
118 views

### Natural deduction proof without assumption

$$(((p\iff q)\iff r)\wedge(q\iff r))\implies p$$ Should be done with natural deduction, but up to $60$ steps. If I assume $\neg\:p$ probably I may finish up to $20$ steps, but without assumption I ...
30 views

### n-formula for k n-evaluations

I am trying to solve the following problem Let $N = \{0, 1, 2, ...\}$ is the set of natural numbers. Propositional variables are $A_{n}$ for $n \in N$ . An evaluation $v$ is called $n$-...
124 views

### Expressing schedule of reinforcement rule using mathematical logic

I am trying to formalize the rules for application of different schedules in a reinforcement learning in special education. Children learn through trials. Each trial is successful if the child ...
158 views

### Help with propositional logic

Hi all this is for a homework where we just started learning logic and I am not very familiar with propositional logic. So we have two problems: To show a proof of the Sherlock Holmes syllogism ...
55 views

### “Truth set” approach to validity and logical consequence: how does it relate to the standard approach? what are the possible drawbacks?

References : I think the " truth set approach" to validity and logical consequence can be linked to the name of R. Carnap ( who defines L-truth and L-implication in this way in his Introduction to ...
38 views

### Can we use induction on the number of connectives?

Usually when we prove some properties of propositional formulas, we use induction on the complexity of propositional formulas, but instead, we can just use induction on the number of occurrence of ...
102 views

### Proof of Validity of My Polynomial Time Algorithm for $co-NP$ Complete Problem

I posted an algorithm yesterday, that purported to solve the co-NP Complete 'Boolean Tautology Problem' in polynomial time. Link to the algorithm : polynomial time algorithm In that post, I presented ...
39 views

### why does a closed circuit represent a false proposition? (Claude Shannon thesis)

In reading through Claude Shannon's paper: A Symbolic Analysis of Relay and Switching Circuits. As a software engineer, I got confused by Shannon's choice to have 0 as representing a closed circuit, ...
78 views

### Alternative sources for a topos theory description of zeroth order logic

I have recently been reading Robert Goldblatt's fantastic book Topoi: The Categorial Analysis of Logic. Through chapters 6-8, Goldblatt produces a topos theoretic approach to zeroth order logic, where ...
124 views

45 views

### Compact witness of satisfiability of a formula in intuitionistic logic

Given a formula in intuitionistic sentential logic, there is a nice, compact textual representation for a witness of its tautology, namely a program in a typed lambda calculus with introduction and ...
If s, j, and b are logical statements, how do I express the statement "s is true and at least one of the others is false"? Is it $s\wedge (\neg j \vee \neg b)$? But wouldn't there be a case for \$\neg ...