84:
74:
53:
172:
to false and evaluate the formula. If the result is false, naturally it is not a tautology. If it is true, then, by the definition of a positive
Boolean formula (and positive Boolean function), it will remain true if you change one or more variables to true. Therefore, it will be true for any pattern of truth values, and thus is a tautology. (For more on positive Boolean functions and formulas, I recommend the excellent book on Boolean functions by Crama & Hammer. The first part is
22:
190:
An addendum: A Boolean function could be true for all inputs (essentially a tautology), but the only way to implement that with a
Boolean formula would be for it to be empty, I guess? So no "normal" positive Boolean formula would be a tautology, as setting all variables to false would always make the
171:
Actually, I believe the part about positive
Boolean formulas is wrong. Unless I'm mistaken, it is quite simple to determine in polynomial time whether a positive Boolen formula is a tautology (and under the assumption P≠NP, this would mean it would not be co-NP-complete). You simply set all variables
176:, and discusses positive functions.) If this is correct, of course the text should be modified, to omit this part. Otherwise, the text should ideally contain a reference or basic argument to show that it's true.
140:
191:
formula false. So in a sense this isn't even a "problem" that could be co-NP-complete – it's just a fact about positive
Boolean formulas (i.e., that they are not tautologies). Or…? --
219:
130:
214:
106:
97:
58:
162:
This article mentions the problem of determining whether a "positive boolean formula", but doesn't explain what that means. ~
33:
21:
196:
181:
173:
39:
83:
192:
177:
105:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
89:
73:
52:
163:
208:
102:
79:
200:
185:
166:
15:
101:, a collaborative effort to improve the coverage of
8:
47:
19:
49:
7:
95:This article is within the scope of
38:It is of interest to the following
14:
220:Low-priority mathematics articles
115:Knowledge:WikiProject Mathematics
118:Template:WikiProject Mathematics
82:
72:
51:
20:
215:Stub-Class mathematics articles
135:This article has been rated as
167:03:32, 16 September 2011 (UTC)
1:
109:and see a list of open tasks.
201:20:17, 27 January 2016 (UTC)
186:19:35, 27 January 2016 (UTC)
236:
134:
67:
46:
158:Positive boolean formula
141:project's priority scale
98:WikiProject Mathematics
28:This article is rated
121:mathematics articles
90:Mathematics portal
34:content assessment
155:
154:
151:
150:
147:
146:
227:
174:available online
123:
122:
119:
116:
113:
92:
87:
86:
76:
69:
68:
63:
55:
48:
31:
25:
24:
16:
235:
234:
230:
229:
228:
226:
225:
224:
205:
204:
160:
120:
117:
114:
111:
110:
88:
81:
61:
32:on Knowledge's
29:
12:
11:
5:
233:
231:
223:
222:
217:
207:
206:
159:
156:
153:
152:
149:
148:
145:
144:
133:
127:
126:
124:
107:the discussion
94:
93:
77:
65:
64:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
232:
221:
218:
216:
213:
212:
210:
203:
202:
198:
194:
188:
187:
183:
179:
175:
169:
168:
165:
157:
142:
138:
132:
129:
128:
125:
108:
104:
100:
99:
91:
85:
80:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
189:
170:
161:
137:Low-priority
136:
96:
62:Low‑priority
40:WikiProjects
112:Mathematics
103:mathematics
59:Mathematics
209:Categories
30:Stub-class
193:Mlhetland
178:Mlhetland
139:on the
164:Booya
36:scale.
197:talk
182:talk
131:Low
211::
199:)
184:)
195:(
180:(
143:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
